Information Limits of Low-Rank Approximation Certification

Kang Liu; Bohao Qu

math.OCOct 2, 2026

Information Limits of Low-Rank Approximation Certification

Authors: Kang Liu, Bohao Qu

Organizations: School of Future Technology, Xi’an Jiaotong University, Xi’an, China. · Centre for Frontier AI Research (CFAR), A*STAR, Singapore.

Abstract

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 $\sqrt{\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 $N^{1/3}$ and $N^{2/3}$ for validation and construction beyond the true target. Code is available at https://anonymous.4open.science/r/Low-rank-approximation-1275/

Figures & tables

Figure 1: Numerical illustrations of the certification theory. (a) The normalized F-tail exponent approaches one. (b) Selected Gaussian validation budgets versus

\log W

; dashed and dotted curves indicate square-root logarithmic and logarithmic reference slopes, respectively. (c) Spectral dispersion changes the relative stopping delays of the two certificates. (d) Independently evaluated costs at selected validation budgets; dashed curves show the asymptotic minimum costs within the two rule families. Legend exponents in (b,d) are descriptive log–log fits. Error bars in (c,d) indicate

\pm 2

Monte Carlo standard errors; those in (d) are conditional on the selected budgets.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Single-candidate bounds. Left: the F-tail lower bound (solid) and exponential upper bound (dashed). Right:

-\log p_{s}(\Delta/2)/(sJ)

, with reference value one. The right panel displays budgets

s\geq 64

for readability.

$d$	$\log_{2}W$	Selected $s$	Error (%)	Interval (%)
8	28	1549	8.997	[8.396, 9.636]
12	66	2295	7.715	[7.157, 8.313]
16	120	2941	10.718	[10.066, 11.406]
24	276	4402	8.533	[7.947, 9.157]
32	496	5881	6.348	[5.840, 6.896]
48	1128	8714	6.519	[6.004, 7.074]

Appendix

Table 1: Width experiment: independently evaluated, screening-selected Gaussian budgets. Error intervals are pointwise Wilson 95% intervals conditional on the selected budget. Here

\log_{2}W=d(d-1)/2

Figure 3: The width mechanism on fixed finite families. (a) Mean and 90th-percentile maximum error at

s=4096

; mean error bars show

\pm 2

Monte Carlo standard errors. (b) Selected query budgets compared with square-root logarithmic and logarithmic reference slopes. (c) Fresh evaluation of the selected budgets, with pointwise Wilson 95% intervals and the screening target marked. The family width is

W=2^{d(d-1)/2}

throughout.

$W$	$s=512$	$s=1024$	$s=2048$	Error percentile
1	82	15	0	0.002509
4	366	43	1	0.003137
16	1123	187	4	0.003767
64	1944	622	11	0.004267
256	2048	1517	43	0.004746
1024	2048	2025	154	0.005131

Appendix

Table 2: Primary-family simultaneous error counts out of 2048 trials per budget, identical for all three check grids. The last column is the empirical 95th percentile of maximum absolute error at

s=2048

Family	Trials	Failures	Error (%)	Interval (%)
1	2048	568	27.734	[25.839, 29.714]
2	512	156	30.469	[26.640, 34.589]
3	512	139	27.148	[23.477, 31.160]

Appendix

Table 3: Independent fixed families at

s=2048

W=4096

. Error probabilities and pointwise Wilson 95% intervals are percentages.

Figure 4: Additional validation-reuse results. Left: empirical 95th percentile of the maximum absolute ratio error, divided by

g

, for the primary family; the dashed line marks the half-gap decision margin. No interval for the percentile is shown. Right: simultaneous error probabilities for all three fixed families at

s=2048

, with pointwise Wilson 95% intervals.

$N$	$M$	$s$	Energy ratio	Block signs
512	1	128	$167.21\pm 1.72$	$263.91\pm 2.04$
512	1	256	$125.88\pm 1.35$	$190.37\pm 1.85$
512	1	512	$91.19\pm 1.04$	$135.18\pm 1.41$
512	512	128	$168.72\pm 0.13$	$17.11\pm 0.22$
512	512	256	$125.54\pm 0.09$	$12.50\pm 0.16$
512	512	512	$91.97\pm 0.07$	$8.91\pm 0.11$

Appendix

Table 4: Complete fixed-budget spectral results: mean positive delay

\pm

one Monte Carlo standard error from 512 paired trials per setting. Adding

s

gives the mean excess cost without changing its standard error.

	Block signs		Energy ratio
$N$	Selected $s$	Cost	Selected $s$	Cost
$2^{12}$	64	$131.40\pm 0.22$	352	$1220.21\pm 0.06$
$2^{15}$	96	$250.26\pm 0.51$	1440	$5054.76\pm 0.09$
$2^{18}$	192	$504.70\pm 1.05$	5792	$20584.19\pm 0.13$
$2^{21}$	352	$998.34\pm 2.18$	23168	$83098.69\pm 0.19$
$2^{24}$	736	$1996.60\pm 4.22$	92672	$333937.20\pm 0.27$

Appendix

Table 5: Independent evaluation at screening-selected budgets. Costs are

s+\mathbb{E}D_{s}

; entries show means

\pm

one Monte Carlo standard error from 8192 fresh trials.

Figure 5: Additional stopping-cost results. (a,b) All fixed-budget spectral settings, with 512 paired trials per setting. Solid curves use

N=2048

and dashed curves use

N=512

. (c) Independent evaluation costs divided by the continuous asymptotic minimum within each rule family. (d) The complete screening grid at

N=2^{21}

; large markers show fresh evaluation at the selected budgets. Error bars in (a–c) are

\pm 2

Monte Carlo standard errors. All costs exclude construction before the true target.

Low-Rank Approximation

Low-rank approximation represents matrices, tensors, and model computations with fewer components to reduce storage and computation while preserving useful structure.

See all 93 papers

Compact Lifted Relaxations for Low-Rank Optimization
Mar 5, 2026Ryan Cory-Wright, Jean PauphiletSemidefinite Programming Nonconvex Optimization
Department of Analytics, Marketing and Operations, Imperial Business School, London, UK · Management Science and Operations, London Business School, London, UK
Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization
Feb 23, 2026Ria Stevens, Fangshuo Liao, Barbara Su +3Combinatorial Optimization Quadratic Programming
Rice University
Near-Optimal Nonconvex Matrix Completion
Sep 15, 2026Jian-Feng Cai, Xiliang Lu, Juntao YouRiemannian Optimization Nonconvex Optimization
Department of Mathematics, Hong Kong University of Science and Technology. · School of Mathematics and Statistics, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China. · School of Artificial Intelligence, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China.

Mar 5, 2026J/K move · Enter open · S save

Compact Lifted Relaxations for Low-Rank Optimization

Ryan Cory-Wright, Jean Pauphilet

Department of Analytics, Marketing and Operations, Imperial Business School, London, UK · Management Science and Operations, London Business School, London, UK

Semidefinite Programming Nonconvex Optimization

Open paper AskPDF arXiv

We develop tractable convex relaxations for rank-constrained quadratic optimization problems over

n \times m

matrices, a setting for which tractable relaxations are typically only available when the objective or constraints admit spectral structure. We derive lifted semidefinite relaxations that do not require such spectral terms. Although a direct lifting introduces a large semidefinite constraint in dimension

n^2 + nm + 1

, we prove that many blocks of the moment matrix are redundant and derive an equivalent compact relaxation that only involves two semidefinite constraints of dimension

nm + 1

and

n+m

, respectively. We also derive a new class of valid inequalities for low-rank problems, which we call projection cuts, that exploit the fact that rank constraints are inherited by linear images of a low-rank matrix, to strengthen our low-rank relaxations substantially. For matrix completion and reduced-rank regression problems, among others, we exploit additional structure to obtain even more compact formulations involving semidefinite matrices of dimension at most the sum of the two dimensions of the low-rank decision matrix (i.e., of size at most

n+m

). Overall, we obtain scalable semidefinite bounds for a broad class of low-rank quadratic problems.

Abstract

Low-Rank Approximation

Explore similar work

Compact Lifted Relaxations for Low-Rank Optimization

Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

Near-Optimal Nonconvex Matrix Completion