ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR12-169 | 27th January 2014 17:25

The Approximate Rank of a Matrix and its Algorithmic Applications

RSS-Feed

Abstract:

We study the $\eps$-rank of a real matrix $A$, defined for any $\eps > 0$ as the minimum rank of a matrix that approximates every entry of $A$ to within an additive $\eps$. This parameter is connected to other notions of approximate rank and is motivated by problems from various topics including communication complexity, combinatorial optimization, game theory, computational geometry and learning theory. Here we give bounds on the $\eps$-rank and use them for algorithmic applications. Our main algorithmic results are (a) polynomial-time additive approximation schemes for Nash equilibria for $2$-player games when the payoff matrices are positive semidefinite or have logarithmic rank and (b) an additive PTAS for the densest subgraph problem for similar classes of weighted graphs. We use combinatorial, geometric and spectral techniques; our main new tool is an efficient algorithm for the following problem: given a convex body $A$ and a symmetric convex body $B$, find a covering a $A$ with translates of $B$.



Changes to previous version:

Modified enumeration algorithm. Corrected errors. Made algorithms deterministic.


Revision #1 to TR12-169 | 21st May 2013 10:34

The Approximate Rank of a Matrix and its Algorithmic Applications





Revision #1
Authors: Noga Alon, Troy Lee, Adi Shraibman, Santosh Vempala
Accepted on: 21st May 2013 10:35
Downloads: 212
Keywords: 


Abstract:

We study the $\eps$-rank of a real matrix $A$, defined for any $\eps > 0$ as the minimum rank over matrices that approximate every entry of $A$ to within an additive $\eps$. This parameter is connected to other notions of approximate rank and is motivated by problems from various topics including communication complexity, combinatorial optimization, game theory, computational geometry and learning theory. Here we give bounds on the $\eps$-rank and use them for algorithmic applications. Our main algorithmic results are (a) polynomial-time additive
approximation schemes for Nash equilibria for $2$-player games when the payoff matrices are
positive semidefinite or have logarithmic rank and (b) an additive PTAS for the densest subgraph problem for similar classes of weighted graphs. We use combinatorial, geometric and spectral techniques; our main new tool is an algorithm for efficiently covering a convex body with translates of another convex body.



Changes to previous version:

Added references to work in communication complexity; added two new co-authors.


Paper:

TR12-169 | 22nd November 2012 01:27

The Approximate Rank of a Matrix and its Algorithmic Applications





TR12-169
Authors: Noga Alon, Santosh Vempala
Publication: 30th November 2012 18:32
Downloads: 611
Keywords: 


Abstract:

We introduce and study the \epsilon-rank of a real matrix A, defi ned, for any  \epsilon > 0 as the minimum rank over matrices that approximate every entry of A to within an additive \epsilon. This parameter is connected to other notions of approximate rank and is motivated by problems from various topics including combinatorial optimization, game theory, computational geometry and learning theory. Here we give bounds on the \epsilon-rank and use them to derive (a) polynomial-time approximation schemes for Nash equilibria of substantially larger classes of 2-player games than previously known and (b) an additive PTAS for the densest subgraph problem on inputs having small \epsilon-rank. We use combinatorial, geometric and spectral techniques; our main new tool is an algorithm for efficiently covering a convex body with translates of another convex body.



ISSN 1433-8092 | Imprint