Source author record

Arman Yousefi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry

Catalog footprint

Research overview

3works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Matrix Balancing in Lp Norms: A New Analysis of Osborne's Iteration

We study an iterative matrix conditioning algorithm due to Osborne (1960). The goal of the algorithm is to convert a square matrix into a balanced matrix where every row and corresponding column have the same norm. The original algorithm was proposed for balancing rows and columns in the $L_2$ norm, and it works by iterating over balancing a row-column pair in fixed round-robin order. Variants of the algorithm for other norms have been heavily studied and are implemented as standard preconditioners in many numerical linear algebra packages. Recently, Schulman and Sinclair (2015), in a first result of its kind for any norm, analyzed the rate of convergence of a variant of Osborne's algorithm that uses the $L_{\infty}$ norm and a different order of choosing row-column pairs. In this paper we study matrix balancing in the $L_1$ norm and other $L_p$ norms. We show the following results for any matrix $A = (a_{ij})_{i,j=1}^n$ , resolving in particular a main open problem mentioned by Schulman and Sinclair. 1) We analyze the iteration for the $L_1$ norm under a greedy order of balancing. We show that it converges to an $ε$ -balanced matrix in $K = O(\min\{ε^{-2}\log w,ε^{-1}n^{3/2}\log(w/ε)\})$ iterations that cost a total of $O(m + Kn\log n)$ arithmetic operations over $O(n\log w)$ -bit numbers. Here $m$ is the number of non-zero entries of $A$ , and $w = \sum_{i,j} |a_{ij}|/a_{\min}$ with $a_{\min} = \min\{|a_{ij}|:\ a_{ij}\neq 0\}$ . 2) We show that the original round-robin implementation converges to an $ε$ -balanced matrix in $O(ε^{-2}n^2\log w)$ iterations totalling $O(ε^{-2}mn\log w)$ arithmetic operations over $O(n\log w)$ -bit numbers. 3) We demonstrate a lower bound of $Ω(1/\sqrtε)$ on the convergence rate of any implementation of the iteration.

preprint2014arXiv

Improved Approximation Algorithms for Earth-Mover Distance in Data Streams

For two multisets $S$ and $T$ of points in $[Δ]^2$ , such that $|S| = |T|= n$ , the earth-mover distance (EMD) between $S$ and $T$ is the minimum cost of a perfect bipartite matching with edges between points in $S$ and $T$ , i.e., $EMD(S,T) = \min_{π:S\rightarrow T}\sum_{a\in S}||a-π(a)||_1$ , where $π$ ranges over all one-to-one mappings. The sketching complexity of approximating earth-mover distance in the two-dimensional grid is mentioned as one of the open problems in the literature. We give two algorithms for computing EMD between two multi-sets when the number of distinct points in one set is a small value $k=\log^{O(1)}(Δn)$ . Our first algorithm gives a $(1+ε)$ -approximation using $O(kε^{-2}\log^{4}n)$ space and works only in the insertion-only model. The second algorithm gives a $O(\min(k^3,\logΔ))$ -approximation using $O(\log^{3}Δ\cdot\log\logΔ\cdot\log n)$ -space in the turnstile model.

preprint2013arXiv

On a Linear Program for Minimum-Weight Triangulation

Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation algorithm, and a variety of effective polynomial- time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT. Here we show the first such connections: for an LP formulation due to Dantzig et al. (1985): (i) the integrality gap is bounded by a constant; (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.