Beyond singular value gaps in randomized subspace approximation

Abstract

The success of randomized range finders (RRFs) is typically analyzed via the singular value gaps of a target matrix $A$. In this work, we show that the so-called Frobenius singular value ratio provides a sharper analysis of an RRF's subspace quality under Gaussian sketching. For any matrix $A$ and any integer $k\ge 0$, we derive an explicit, closed-form expression for the cumulative distribution function of the largest principal angle between the $k$-dominant singular subspace of $A$ and the approximate RRF subspace, expressing it in terms of a hypergeometric function. We obtain definitive probabilistic guarantees for RRFs that are strictly stronger than those obtained previously.

27 pages, 4 figures