Timezone: »

Optimal Analysis of Subset-Selection Based L_p Low-Rank Approximation
Chen Dan · Hong Wang · Hongyang Zhang · Yuchen Zhou · Pradeep Ravikumar

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #226
We show that for the problem of $\ell_p$ rank-$k$ approximation of any given matrix over $R^{n\times m}$ and $C^{n\times m}$, the algorithm of column subset selection enjoys approximation ratio $(k+1)^{1/p}$ for $1\le p\le 2$ and $(k+1)^{1-1/p}$ for $p\ge 2$. This improves upon the previous $O(k+1)$ bound (Chierichetti et al.,2017) for $p\ge 1$. We complement our analysis with lower bounds; these bounds match our upper bounds up to constant 1 when $p\geq 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. Our analysis results in improvements on approximation guarantees of 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)$ number of columns. We show that this algorithm has an approximation ratio of $O((k+1)^{1/p})$ for $1\le p\le 2$ and $O((k+1)^{1-1/p})$ for $p\ge 2$. This improves over the bound in (Chierichetti et al.,2017) 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.

Author Information

Chen Dan (Carnegie Mellon University)
Hong Wang (Massachusetts Institute of Technology)
Hongyang Zhang (TTIC)
Yuchen Zhou (University of Wisconsin, Madison)
Pradeep Ravikumar (Carnegie Mellon University)

More from the Same Authors