Matrix-Vector Query Bounds Match for Low-Rank Approximation

Low-rank approximation is commonly evaluated by runtime, memory, or passes over a matrix. This paper isolates a more basic resource: how many exact products with an unknown matrix $A$ or its transpose are needed before an algorithm can construct a useful low-rank approximation. At each step, the algorithm may choose a vector $v$ and observe $Av$, or choose $u$ and observe $A^\top u$; both choices may depend on every previous query, response, and source of private randomness.

The target is deliberately stringent. The algorithm must return a rank-$k$ right projector whose Schatten-$p$ residual is at most $1+\varepsilon$ times the optimal rank-$k$ residual, and it must do so with probability at least $2/3$ for every input matrix. The paper establishes matching polynomial query bounds for that task. Its contribution is therefore a characterization of oracle complexity, rather than a new implementation benchmark or a numerical speed comparison.

Core Contribution

The central result pairs an upper bound with a lower bound in the same adaptive matrix-vector oracle model. The lower bound is the more consequential component: it applies even when an algorithm chooses later left or right probes after seeing the complete earlier transcript. That rules out an apparent escape route in which adaptivity might uncover a hard subspace with substantially fewer products than a fixed-probe method.

The authors define $N=\min\{m,n\}$ and formulate the worst-case budget $Q_p^*$ for success probability $2/3$. Their result concerns the polynomial dependence of this budget on the approximation parameters and dimensions. In practical terms, it separates improvements that can come from better numerical methods from improvements that would require extra assumptions about the input matrix or a richer access model.

Technical Approach

The lower-bound proof uses a randomized hard family whose important spectral directions cannot be identified quickly from adaptive products. A successful projector must overlap sufficiently with a planted subspace; otherwise, its complementary subspace retains spectral mass that produces too large a Schatten-$p$ residual. The proof turns that geometric requirement into a statement about what information remains hidden after a limited query transcript.

A technical part of the argument studies rectangular Gaussian blocks and associated Wishart spectra. The construction transforms a Wishart matrix into a positive semidefinite instance whose eigenvalues separate the directions that a good projector must recover from those it may safely discard. The hard-edge analysis controls small singular values of Gaussian blocks left unexplored after the adaptive interaction.

This is more demanding than a nonadaptive lower bound. The posterior distribution of the unexplored matrix block must remain analyzable after each query is selected from the preceding answers. The paper’s argument uses conditional structure in the transcript, spectral interlacing, and Gaussian small-singular-value behavior to maintain that control. A residual certificate then connects the surviving hard-edge spectrum to failure of the $(1+\varepsilon)$ approximation requirement.

Results and Analysis

The evidence is formal rather than empirical. The paper does not present a dataset benchmark, wall-clock timing study, or approximation-error plot. Instead, its result is a matched upper/lower-bound statement for the exact query model. The main performance condition is explicit: a rank-$k$ projector must achieve residual at most $1+\varepsilon$ times optimum with probability $2/3$.

That distinction matters when interpreting the contribution. The work does not show that one practical randomized SVD implementation runs faster than another. It shows that, under exact products with $A$ and $A^\top$, the polynomial-scale number of observations required for the stated approximation guarantee cannot be improved beyond the matching construction. For researchers developing iterative low-rank methods, that is useful negative information: an algorithm claiming a substantially better polynomial query dependence must be exploiting a changed assumption, a weaker objective, or an error in the analysis.

Limits of the Result

The paper’s scope is intentionally narrow. Each matrix-vector product is exact, and the model counts queries rather than floating-point cost, communication, memory traffic, or numerical stability. The result therefore does not directly prescribe the fastest implementation on finite-precision hardware. It also does not evaluate noisy products, approximate linear solves, structured matrices, or data distributions that can make low-rank approximation easier than the worst case.

The stated result resolves polynomial query behavior, while exact logarithmic factors remain outside the claim. Its multiplicative residual objective is also sensitive to inputs with zero optimal rank-$k$ residual, a feature that is relevant to the hard-instance construction. The paper is best read as a sharp oracle-complexity result, not as a universal practical performance guarantee.