Optimal Analysis of Subset-Selection Based L_p Low-Rank Approximation

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.