PaperlayerView exact revision on arXiv

Source-linked AI summary

Matrix-Vector Complexity of Low-Rank Approximation

Haihan Zhang, Wendao Wu, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin

arXiv:2609.35840v2math.OCcs.DS

TL;DR

The paper asks how many adaptive exact matrix–vector products are needed for relative-error low-rank approximation across Schatten norms. It extends adaptive Wishart lower-bound techniques to a rectangular factor with a k-dimensional nullspace, establishing rank-dependent lower bounds. Together with existing upper bounds, the results give fixed-norm rates and identify a transition as pε grows.

  • Problem

    The paper studies the query cost of finding a rank-k projector with Schatten-p residual at most 1 + ε times optimal using adaptive exact matrix–vector products.

    Source: §1 · p. 2

  • Method

    The proof extends adaptive Wishart decomposition to a rectangular Gaussian factor with a hidden k-dimensional nullspace and analyzes posterior overlap for adaptive outputs.

    Source: §1 · p. 3

  • Results

    For every fixed finite p, the results give eΘ_p(min{N, kε^-1/3}); for growing p, norm dependence transitions when pε is of order one toward the spectral polynomial rate.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Posterior overlap explains the multiplicative rank factor for fixed finite Schatten parameters, while spectral-profile persistence identifies the added cost of increasing p and its transition to the spectral rate.

    Source: §10 · pp. 24–25

    The results concern exact real-valued products with uncharged computation, leave exact logarithmic factors open, and do not characterize noisy or finite-precision oracles.

    Source: §10 · p. 25

Abstract

from arXiv · show

We establish matching polynomial query bounds for low-rank approximation from exact matrix--vector products. Given an unknown matrix $A\in\mathbb{R}^{m\times n}$, at each step a randomized algorithm chooses either $v\in\mathbb{R}^n$ and receives $Av$, or $u\in\mathbb{R}^m$ and receives $A^\top u$. The choice may depend measurably on all previous queries and replies and on the algorithm's private randomness; each vector product costs one query. The output is a rank-$k$ right projector with Schatten-$p$ residual at most $1+\varepsilon$ times optimal. Write $N=\min\{m,n\}$ and let $Q_p^*$ denote the worst-case query budget for success probability $2/3$ on every input. For every $1\le k<N$ and sufficiently small $\varepsilon$, our lower bounds, combined with existing Krylov upper bounds, give $Q_p^*=\widetilde{\Theta}\!\left(\min\{N,k\min\{p^{1/6}\varepsilon^{-1/3},\varepsilon^{-1/2}\}\}\right)$ $(2\le p<\infty)$, $Q_\infty^*=\widetilde{\Theta}\!\left(\min\{N,k\varepsilon^{-1/2}\}\right)$. These bounds have universal constants and allow $p$ to vary with the problem parameters, identifying the transition at $p\varepsilon\asymp1$. A complementary result for each fixed $1\le p<2$ gives $\widetilde{\Theta}_p(\min\{N,k\varepsilon^{-1/3}\})$, with constants and an accuracy threshold that may depend on $p$. Together, the results recover this fixed-norm rate for every fixed finite $p$, supplying the multiplicative rank dependence missing from previous lower bounds. Tildes suppress logarithmic factors. The proof extends adaptive Wishart deferred decisions to a rectangular factor with a $k$-dimensional nullspace. Posterior overlap gives a short fixed-norm argument, while persistence of small compression eigenvalues controls growing $p$ and the spectral endpoint. Exact range recovery handles target costs of order $k$; the Wishart family covers the remaining regimes.

1 Introduction

The paper studies relative-error rank-k approximation from adaptive exact matrix–vector products, asking how many queries suffice across Schatten norms. Its lower bounds recover multiplicative rank dependence and extend through the transition to spectral approximation.

1 Introduction

  • The task is to find a rank-k projector whose Schatten-p residual is within 1 + ε of optimal, using adaptive exact products Av or Aᵀu.Success probability must be at least 2/3 on every input; computation between queries is uncharged.Source: §1 · p. 2
  • Earlier lower bounds did not explain the product of rank and accuracy costs, even for Frobenius approximation.The cited Frobenius comparison records an additive frontier Ω(k + ε^-1/3) in sufficiently large dimension.Source: §1 · p. 2
  • For every fixed finite Schatten parameter, the results recover a rate of eΘ_p(min{N, kε^-1/3}), while extending the lower bound through the transition to spectral approximation.The norm dependence grows as p^1/6 until pε is of order one, then reaches the spectral polynomial rate; logarithmic factors are suppressed.Source: §1 · p. 2
  • The proof uses a rectangular Wishart factor with a hidden k-dimensional nullspace, forcing relative approximation to capture a constant fraction of that nullspace.The shifted matrix is H = I − W/L, and the adaptive Wishart decomposition applies to arbitrary transcript-dependent rank-k outputs.Source: §1 · p. 3
  • At dimension d ≍ p kε^-1/3, the positive spectral edge together with the overlap inequality forces q = Ω(d) queries.This provides a lower-bound mechanism for the multiplicative rank-accuracy cost.Source: §1 · p. 3

2 Related Work

Prior work develops randomized and Krylov algorithms, adaptive Wishart lower bounds, and random-matrix estimates. This paper builds on those tools while targeting adaptive exact matvec lower bounds with joint rank–accuracy dependence.

2 Related Work

  • Randomized range finding and matrix decompositions provide a modular framework, while block Krylov methods improve spectral approximation accuracy dependence [6].BCW sharpen finite Schatten-norm query bounds [1], and Bakshi and Narayanan remove input-dimension dependence from the fixed-p rank-one upper bound up to accuracy logarithms.Source: §2 · p. 3
  • Single-vector Krylov analyses address spectral gaps and random perturbations [7], while later work studies intermediate block sizes [8] and arithmetic or finite-precision issues [9].The upper bounds used in this paper are specifically those of BCW and Musco–Musco; its lower bound addresses information required by any adaptive algorithm.Source: §2 · p. 4
  • Adaptive Wishart decompositions support oracle lower bounds for regression and eigenvalue estimation, and shifted square Wishart matrices were used for low-rank approximation [1].This paper uses a rectangular factor with exactly k missing columns and tracks posterior covariance outside the query span and nullspace mass accumulated inside it.Source: §2 · p. 4
  • Rectangular singular-value estimates and intermediate-singular-value bounds compare spectral profiles [11, 12], while hard-edge laws supply a probability margin at bounded rank.The paper applies these distributional inputs to arbitrary adaptive output complements to obtain the margin needed for success probability 2/3.Source: §2 · p. 4

3 Oracle Model and Main Results

The section specifies an adaptive exact matrix–vector query model and establishes lower-bound results across Schatten norms, including fixed-norm rates and a transition for growing p. It also explains the proof branches and how square hard instances transfer to rectangular inputs.

3 Oracle Model and Main Results

  • The results use exact adaptive products Av or A⊤u, count each vector product as one query, and require a rank-k projector to meet the residual criterion with probability at least 2/3.The query budget is a worst-case upper limit, not an expected count; computation and storage are uncharged.Source: §3 · pp. 4–5
  • For each fixed 1≤p<∞, the query rate is ~Θ_p(min{N,kε^-1/3}); for p≥2, the uniform theorem’s polynomial transition occurs at pε≈1.The fixed-p constants and accuracy threshold may depend on p, unlike the universal constants in the uniform theorem.Source: §3 · pp. 5–6
  • At k=N-r, finite-p complexity is ~Θ(min{N,(N-r)Φ(p,ε)}), while p=∞ gives ~Θ(min{N,(N-r)/√ε}); fixed codimension yields linear complexity as N grows.The finite-p rate is linear up to logarithms when (N-r)Φ(p,ε)≥N; the spectral rate is linear when N-r≥N√ε.Source: §3 · p. 6

3.1 Why the rank and accuracy costs multiply

  • Exact recovery of a generic rank-k Gaussian range handles target costs of order k; otherwise, a rectangular Wishart family supplies the lower-bound construction.The second branch includes the regime where the target cost reaches N while N≫k.Source: §3.1 · p. 6
  • Posterior overlap bounds apply to arbitrary transcript-measurable outputs and force overlap of at least 3k/4 when d≲p kε^-1/3 on a high-probability spectral event.This argument proves the below-two proposition and also gives a direct proof of the fixed-finite-norm corollary.Source: §3.1 · p. 6
  • For growing p, small eigenvalues persist in the output complement after adaptive queries, and comparing Θ(k) modes with the optimal residual yields the stated accuracy thresholds.The comparison gives d^3≲k^3√p/ε in one regime and the spectral scale d≲k/√ε in another; bounded k uses a one-mode separation.Source: §3.1 · p. 6

3.2 Embedding the hard dimension

  • Zero-padding transfers a square hard-instance lower bound to rectangular inputs while preserving the optimal tail singular values and allowing each padded query to be simulated with one original product.The reduction compares residual norms for arbitrary padded output subspaces.Source: §3.2 · pp. 6–7

4 Adaptive Gaussian Information

The paper extends adaptive Gaussian conditioning to a rectangular factor with a k-dimensional nullspace, then uses the resulting information bounds to establish exact-recovery and overlap baselines.

4.1 A rectangular deferred-decision theorem

  • The rectangular factorization tracks both the information exposed by queries and the independent Gaussian portion that remains hidden.The theorem conditions on the actual transcript while retaining a fixed product-Gaussian law for the unobserved block.Source: §4.1 · pp. 7–8
  • Conditioning on adaptive queries leaves an unobserved Gaussian block independent of the enlarged transcript, extending the deferred-decision argument to rectangular factors.The factorization applies to W = XX⊤ when X has independent Gaussian entries and fewer columns than rows.Source: §4.1 · pp. 7–8

4.2 Exact recovery as the rank baseline

  • Exactly rank-k positive semidefinite inputs require k queries for exact relative-error recovery, and k generic Gaussian queries suffice to recover their range.The lower bound follows because relative-error success with zero optimal residual forces exact range recovery.Source: §4.2 · pp. 9–10

4.3 Posterior nullspace overlap

  • After adaptive queries, the expected overlap between the output projector and the hidden nullspace is bounded, ruling out substantial overlap when both query count and rank are small relative to dimension.The posterior-overlap theorem applies to every transcript-measurable rank-k projector.Source: §4.3 · p. 11

5 The Fixed-Norm Lower Bound

The fixed-norm lower bound converts missing information about a hidden nullspace into Schatten approximation error, then uses that obstruction to obtain the rank-dependent query bound.

5.1 A well-conditioned hard family

  • A shifted rectangular Wishart construction yields a well-conditioned matrix whose top-k eigenspace is the Wishart factor's nullspace.On the stated spectral event, H has spectrum in [1/2, 1] and top-k eigenspace K.Source: §5.1 · p. 12
  • Relative Schatten-p approximation on the hard family forces the output projector to capture a constant fraction of the hidden k-dimensional nullspace.For sufficiently small η_p and d ≤ η_p k ε^-1/3, the stated overlap is at least 3k/4.Source: §5.1 · p. 12

5.2 Completing the fixed-norm bound

  • Posterior-overlap bounds and the hard family give an Ω_p(R) query lower bound, which combines with the existing upper bound and exact recovery to establish the fixed-norm rate.The argument treats small target budgets using a Gaussian rank-k instance and larger budgets using the Wishart construction.Source: §5.2 · p. 13

6 Spectral Information Beyond Total Overlap

The growing-norm analysis compares the small-eigenvalue profile left in an output complement with the rectangular Wishart spectrum, including a separate edge argument for bounded rank.

6.1 Rectangular spectral profile

  • Lemma 6.1 establishes a uniform rectangular lower-spectrum event with probability at least 0.995 for every d ≥ d0 and 1 ≤ k ≤ d/4, uniformly down to k = 1.Source: §6.1 · p. 14

6.2 Adaptive persistence of small eigenvalues

  • After q adaptive queries, for almost every transcript and conditional on Fq, the intermediate-persistence event holds with probability at least 0.95 for all indices 1≤j≤h.Source: §6.2 · p. 15

6.3 Bounded-rank edge separation

  • For bounded rank, exact hard-edge distributional separation supplies a strict probability margin that coarse spectral bounds do not provide.The margin is needed after intersecting the edge events with auxiliary spectral events to retain the probability required for the minimax theorem.Source: §6.3 · pp. 16–18

7 From Spectral Profiles to Schatten Error

The section translates spectral compression bounds into excess Schatten residual, using multimode comparisons at larger rank and a one-mode comparison at bounded rank.

7 From Spectral Profiles to Schatten Error

  • Poincaré separation makes each term in the output residual's excess over the optimal residual nonnegative.The comparison is made between the compressed spectrum and the optimal rank-k spectrum.Source: §7 · p. 19
  • For large rank, comparing Θ(k) compressed modes with the optimal spectrum yields excess residual bounds, with a separate exponential comparison when the dimensionless parameter is large.The large-rank result distinguishes the regimes a² = pk²/d² = O(1) and a² above a universal threshold.Source: §7 · pp. 19–20
  • For bounded rank, a one-mode comparison uses the finite-codimension edge separation to control the residual at growing p.The exponential comparison reflects the larger residual power when the output complement retains an eigenvalue below the optimal edge.Source: §7 · pp. 20–21

8 Completing the Uniform Lower Bounds

The lower-bound proof handles both target costs of order k and larger costs, where the rectangular Wishart construction is needed. Its finite-p and spectral endpoint arguments combine with exact recovery and spectral Krylov iteration to establish the stated bounds.

8 Completing the Uniform Lower Bounds

  • For R*=O(k), exact range recovery gives q=Ω(R*) without restricting k/N; when R*=N≫k, the Wishart branch remains necessary.This covers the near-full-rank baseline branch as well as saturation caused by stringent accuracy.Source: §8 · p. 21
  • For both k≥K⋆ and bounded k, every q≤αd algorithm fails with probability above 1/3, yielding the finite-p lower bound by Yao’s principle.The large-rank case has a failure event of probability at least 0.9; the bounded-rank case has probability strictly above 1/3.Source: §8 · pp. 22–23
  • The spectral endpoint proof also treats large and bounded ranks, then uses Yao’s principle and spectral Krylov iteration with exact recovery to prove (6).The bounded-rank case uses a finite-codimension event with probability strictly greater than 1/3.Source: §8 · p. 24

9 Inherited Upper Bounds and the Transition

The paper inherits its upper bounds from existing Schatten approximation and Krylov algorithms, converting left-projector guarantees when needed. The resulting bounds cover finite p through a transition corridor and the spectral endpoint.

9 Inherited Upper Bounds and the Transition

  • When n>m, running the algorithm on Aᵀ and converting its left projector to a right projector preserves the guarantee at a cost of k further products.The conversion uses AᵀU and completes the resulting range to rank k when necessary.Source: §9 · p. 24
  • For 1≤p≲log(N)/ε, the BCW guarantee uses products with success probability at least 9/10; the two terms yield rate Õ(kΦ) across the stated corridor.When pε≤1, the p^1/6ε^-1/3 term governs; when 1≤pε≲log N, both terms are bounded by kε^-1/2 up to logarithmic factors.Source: §9 · p. 24
  • For p≥C log N/ε, spectral block Krylov iteration requires Õ(k/√ε) products, and the same algorithm directly handles p=∞.The upper bound takes the smaller of the applicable algorithm budget and N.Source: §9 · p. 24

10 Discussion

The discussion distinguishes the overlap argument for fixed norms from spectral-profile persistence for growing p. It also states the model and scope boundaries for the results.

10 Discussion

  • Posterior overlap explains the multiplicative rank factor for fixed finite Schatten parameters, while spectral-profile persistence captures the added cost as p grows and the transition to the spectral rate.The upper bounds are inherited; the paper’s contribution is the adaptive lower bound with joint parameter dependence.Source: §10 · pp. 24–25
  • When the target rate reaches N, complexity is linear up to logarithms; exactly rank-k inputs have zero optimal residual, making the worst-case multiplicative model essential.A full-rank promise or a positive lower bound on the optimal tail would require separate analysis of the baseline branch.Source: §10 · p. 25
  • The results leave exact logarithmic factors open and concern exact real-valued products with uncharged computation, not noisy or finite-precision oracles.Constants are not claimed uniform over 1≤p<2, and no confidence-dependent minimax characterization is asserted.Source: §10 · p. 25

Related papers

Loading 2609.35840v2…