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.