Optimal analysis of subset-selection based lp low-rank approximation

Chen Dan, Hongyang Zhang, Hong Wang, Yuchen Zhou, Pradeep Ravikumar

Research output: Contribution to journalConference articlepeer-review


We study the low rank approximation problem of any given matrix A over Rn×m and Cn×m in entry-wise lp loss, that is, finding a rank-k matrix X such that kA - Xkp is minimized. Unlike the traditional l2 setting, this particular variant is NP-Hard. We show that the algorithm of column subset selection, which was an algorithmic foundation of many existing algorithms, enjoys approximation ratio (k + 1)1/p for 1 = p = 2 and (k + 1)1-1/p for p = 2. This improves upon the previous O(k + 1) bound for p = 1 [1]. We complement our analysis with lower bounds; these bounds match our upper bounds up to constant 1 when p = 2. At the core of our techniques is an application of Riesz-Thorin interpolation theorem from harmonic analysis, which might be of independent interest to other algorithmic designs and analysis more broadly. As a consequence of our analysis, we provide better approximation guarantees for several other algorithms with various time complexity. For example, to make the algorithm of column subset selection computationally efficient, we analyze a polynomial time bi-criteria algorithm which selects O(k log m) columns. We show that this algorithm has an approximation ratio of O((k + 1)1/p) for 1 = p = 2 and O((k + 1)1-1/p) for p = 2. This improves over the best-known bound with an O(k + 1) approximation ratio. Our bi-criteria algorithm also implies an exact-rank method in polynomial time with a slightly larger approximation ratio.

Original languageEnglish (US)
JournalAdvances in Neural Information Processing Systems
StatePublished - 2019
Event33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019 - Vancouver, Canada
Duration: Dec 8 2019Dec 14 2019

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Optimal analysis of subset-selection based lp low-rank approximation'. Together they form a unique fingerprint.

Cite this