TY - GEN

T1 - The approximate rank of a matrix and its algorithmic applications

AU - Alon, Noga

AU - Lee, Troy

AU - Shraibman, Adi

AU - Vempala, Santosh

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2013

Y1 - 2013

N2 - We study the ε-rank of a real matrix A, defined for any ε > 0 as the minimum rank over matrices that approximate every entry of A to within an additive ε. 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 ε-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.

AB - We study the ε-rank of a real matrix A, defined for any ε > 0 as the minimum rank over matrices that approximate every entry of A to within an additive ε. 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 ε-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.

KW - Approximate rank

KW - Convex body

KW - Covering number

KW - Nash equilibria

UR - http://www.scopus.com/inward/record.url?scp=84879812360&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879812360&partnerID=8YFLogxK

U2 - 10.1145/2488608.2488694

DO - 10.1145/2488608.2488694

M3 - Conference contribution

AN - SCOPUS:84879812360

SN - 9781450320290

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 675

EP - 684

BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing

T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013

Y2 - 1 June 2013 through 4 June 2013

ER -