Replacing the matrix in an iteration with random low-rank matrices can reduce the cost of matrix-vector multiplication. However, even if the sampled matrices equal the original matrix in expectation, the expected squared norm of the random iterates may grow while the original iteration converges. Under a fixed rank bound, we study how to choose the distribution of these random matrices to minimize this growth when sampling independently at each step. We derive an exact formula for the optimal asymptotic growth factor and use it to determine when the expected squared norm can converge to zero. We then characterize precisely when a fixed sampling distribution achieves this optimal factor and construct finite-support optimal distributions in every attainable case. These results determine the minimum rank required for stability and provide optimal sampling designs under the prescribed rank constraint.
Figures & tables
Law
Frobenius MSE
Error moment
Raw moment
g(μ)
Spectral
0.72
0.36
1.17
1.17
Dense
0.72
0.36
1.17
0.97
P=I sampler
0.97
0.81
0.97
0.97
Table 1: Three unbiased rank-one laws. The error and raw moments are ∥E[(R−A)⊤(R−A)]∥2 and ∥E[R⊤R]∥2 , respectively.
Figure 1: Mean-square trajectories of the three sampling laws, computed from their second-moment recursions with x0=e1 . The main plot uses a logarithmic vertical axis; the inset shows the first twelve steps of the two stable laws.
Figure 2: Effect of coordinate choice on mean-square growth. (a) Growth factors as η varies, with r=2 . (b) Growth factors as r varies, with η=6 . (c) Worst expected squared norms ak for η=6 and r=2 . In (a)–(b), the growth factor is labeled ρ(Mμ)=g(μ) , where Mμ(X)=Eμ[RXR⊤] is the second-moment operator; the horizontal dotted line marks the stability boundary g=1 . Solid, dotted, and dashed curves correspond to the Euclidean moment, Frobenius, and transformed samplers, respectively.
Sampler
g(μ)
a1
a60
Euclidean moment
0.9687
2.2287
0.4483
Frobenius
0.9594
2.2287
0.2568
Transformed
0.5625
7.2290
3.76×10−14
Table 2: Growth factors and worst expected squared norms for η=6 and r=2 .
Mean A , up to similarity
r
b(A)
ν0(A)
N
qr(A)=g(μ)
diag(1,2,J3(0))
1
2
3
4
5
diag(C,J2(0))
1
1
2
4
4
diag(1,1,J3(0))
2
2
3
4
1
diag(B,J3(0))
1
2
3
4
2
diag(H,J3(0))
2
2
3
8
4
diag(1,1,J3(0),J2(0))
2
2
3
8
1
Table 3: Finite-support optimal distributions covering the three attainment regimes. In every row, the constructed distribution satisfies ER=A , rankR≤r almost surely, and g(μ)=qr(A) . The column N counts entries in the finite sampling list.
ε
g(με)
Gap
E∥R∥F2
0.40
0.6800
0.3200
9.1800
0.20
0.4400
0.0800
22.4400
0.10
0.3800
0.0200
76.3800
0.05
0.3650
0.0050
292.3650
0.02
0.3608
0.0008
1804.3608
0.01
0.3602
0.0002
7204.3602
Table 4: A three-point sampling family approaching the unattained optimal value 0.36 . The gap is g(με)−0.36 .
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
ε
ρ(Mε)
ρ(Mε)−0.36
E∥R∥F2
0.40
0.6800
0.3200
9.1800
0.20
0.4400
0.0800
22.4400
0.10
0.3800
0.0200
76.3800
0.05
0.3650
0.0050
292.3650
0.02
0.3608
0.0008
1804.3608
0.01
0.3602
0.0002
7204.3602
Appendix
Table B.1: Six sampling scales approaching the unattained optimal value 0.36 . Each distribution has three support matrices.
Mean, up to similarity
d
r
N
qr(A)
Sample ranks
χM(z)
diag(1,2,J3(0))
5
1
4
5
1
z13(z−5)2
diag(C,J2(0))
4
1
4
4
1
z9(z−4)
diag(1,1,J3(0))
5
2
4
1
2
z12(z−1)3
diag(B,J3(0))
5
1
4
2
1
z13(z−2)2
diag(H,J3(0))
7
2
8
4
2
z25(z−4)3
diag(1,1,J3(0),J2(0))
7
2
8
1
2
z25(z−1)3
Appendix
Table B.2: Complete data for eight finite-support optimal distributions. The sample-rank column lists all ranks occurring in each distribution.
Law
Frobenius MSE
Centered moment
Raw moment
g(μ)
Spectral
0.72
0.36
1.17
1.17
Dense
0.72
0.36
1.17
0.97
Raw optimal
0.97
0.81
0.97
0.97
Appendix
Table C.1: Three unbiased rank-one laws with mean diag(0.9,0.4) . The first two share the entire right second-moment matrix. The centered and raw columns give the largest eigenvalues of the corresponding moment matrices.
Figure C.1: Second moments computed by deterministic recursions. Left: the three laws in Table C.1 , starting from e1 , with an inset showing the initial behavior of the two stable laws. Right: the Jordan law ( C.16 ) with a=0.6 and b=4 , starting from e2 ; the inset shows Γ1,K=0.72+16/K . All expectations are evaluated over the complete finite support.
Sampling objective
Raw moment
Centered moment
Frobenius MSE
Raw moment
1.3823
1.3750
13.8233
Centered moment
1.8544
0.8544
10.2524
Frobenius MSE
2.3282
1.3282
8.0764
Appendix
Table C.2: One-step criteria for the geometric-spectrum 15×12 target at rank two. Each row minimizes its named objective.
Figure C.2: Directional moments of dense 15×12 targets with three singular spectra. Each curve is evaluated over the complete support of its law, with every realization of rank exactly r . The top row gives λmax(E[R⊤R]) and the bottom row gives λmax(E[(R−B)⊤(R−B)]) .
Mean or specified law
Attainment
Uniform bound
Quadratic certificate
diag(a,J3(0))
No
No
No
diag(a,J2(0))
Yes
Every optimal law
No
Law ( C.16 ) for Ab
Yes
No
No
Appendix
Table C.3: Attainment and bounds at the optimal factor for rank one. Here a=0 , and b=0 in the last row. The first two rows concern existence among admissible laws; the last row concerns the specified law in ( C.16 ). A uniform bound means E∥xk∥22≤Cq1(A)k∥x0∥22 for all x0 and k≥0 .
Figure C.3: Exact conditioning tradeoffs for A=(0.5010.5+δ) . Left: δ=0 , comparing the excess above each rank-dependent optimum. Right: rank one and three eigenvalue separations; dotted lines mark the finite cutoffs K⋆ beyond which the excess is exactly zero. The zero portions are omitted on the logarithmic scale.
Low-rank approximation represents matrices, tensors, and model computations with fewer components to reduce storage and computation while preserving useful structure.
We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an n×n positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared ℓ2-norm. The algorithm runs in just O(n) expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.
Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco +1
University of Massachusetts Amherst · University of California Berkeley
Low-rank approximation can require additional matrix--vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across W paths, a concentration bound exploiting shared residual energy yields a log(W+1) dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders N1/3 and N2/3 for validation and construction beyond the true target. Code is available at https://anonymous.4open.science/r/Low-rank-approximation-1275/
Kang Liu, Bohao Qu
School of Future Technology, Xi’an Jiaotong University, Xi’an, China. · Centre for Frontier AI Research (CFAR), A*STAR, Singapore.
Given a matrix M∈Rm×n, the low rank matrix completion problem asks us to find a rank-k approximation of M as UV⊤ for U∈Rm×k and V∈Rn×k by only observing a few entries specified by a set of entries Ω⊆[m]×[n]. In particular, we examine an approach that is widely used in practice -- the alternating minimization framework. Jain, Netrapalli, and Sanghavi [JNS13] showed that if M has incoherent rows and columns, then alternating minimization provably recovers the matrix M by observing a nearly linear in n number of entries. While the sample complexity has been subsequently improved [GLZ17], alternating minimization steps are required to be computed exactly. This hinders the development of more efficient algorithms and fails to depict the practical implementation of alternating minimization, where the updates are usually performed approximately in favor of efficiency. In this paper, we take a major step towards a more efficient and error-robust alternating minimization framework. To this end, we develop an analytical framework for alternating minimization that can tolerate a moderate amount of errors caused by approximate updates. Moreover, our algorithm runs in time O(∣Ω∣k), which is nearly linear in the time to verify the solution while preserving the sample complexity. This improves upon all prior known alternating minimization approaches which require O(∣Ω∣k2) time.
Yuzhou Gu, Zhao Song, Junze Yin +1
Institute of Advanced Study. · Adobe Research. · Boston University +1