PaperlayerView exact revision on arXiv

Source-linked AI summary

Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO

Richard Y. Zhang

arXiv:2608.29018v1stat.MLcs.ITcs.LGmath.OCmath.ST

TL;DR

The paper asks whether penalized rank-restricted matrix LASSO can achieve both the optimal recovery rate and the sharp RIP threshold at global minima. It develops a defect-preserving recovery argument and adversarial counterexamples, showing that the sharp threshold is attainable, unimprovable, and independent of search rank when the search space contains the ground truth.

  • Problem

    Prior analyses of penalized LASSO either sacrificed the sharp RIP threshold or the optimal error rate, while the estimator may have greater nuclear norm than the ground truth.

    Source: §II · pp. 3–4

  • Method

    The proof retains an additive defect in the head-tail inequality and combines it with a sharp head estimate, while necessity uses a two-block adversarial construction.

    Source: §III · p. 6, §IV · p. 8, §VI · p. 13

  • Results

    If δ < δsharp(k/r⋆), every global minimizer achieves the stated optimal error bound, whereas beyond the threshold counterexamples can make every global minimizer fail; the threshold is therefore sharp.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    At global optimality, the recovery threshold depends on the ground-truth rank rather than the search rank, so rank overparameterization is not itself a statistical obstruction.

    Source: §VI · p. 13

Abstract

from arXiv · show

We determine the sharp restricted isometry threshold for recovery at global minima of the rank-restricted matrix LASSO. For target rank $r_{\star}$, if the rank-$k$ RIP constant satisfies $δ<δ_{\mathrm{sharp}}(k/r_{\star})$, where $δ_{\mathrm{sharp}}(t)=t/(4-t)$ for $0<t<4/3$ and $δ_{\mathrm{sharp}}(t)=\sqrt{(t-1)/t}$ for $t\ge4/3$, then every global minimizer has Frobenius error $\lesssim\sqrt{r_{\star}}λ$ for all $λ\gtrsim\|\mathcal{A}^{*}(ξ)\|_{\mathrm{op}}$ and at every search rank $r\ge r_{\star}$. The constants depend only on the RIP constant and $t=k/r_{\star}$, and in particular are independent of the search rank. When the rank restriction is inactive, the result specializes to the ordinary convex matrix LASSO. We also obtain the analogous results for sparsity-restricted vector LASSO. Conversely, we show that the threshold $δ<δ_{\mathrm{sharp}}(k/r_{\star})$ cannot be improved, due to the existence of counterexamples whose global minimizers fail to recover the ground truth.

I. INTRODUCTION

The paper characterizes recovery at global minima of rank-restricted matrix LASSO under RIP, obtaining a sharp threshold, optimal error scaling, and search-rank-independent guarantees. It also shows sharpness, convex-relaxation consequences, and the distinction between statistical recovery at global minima and the difficulty of finding them.

Problem and formulation

  • Low-rank matrix recovery estimates an unknown rank-at-most-r⋆ matrix from noisy linear measurements using a factored, rank-restricted LASSO formulation.The estimator can be viewed either as nonconvex optimization over factors or as nuclear-norm penalization with a rank cap.Source: §I · p. 1
  • The paper addresses recovery guarantees at global minima because existing second-order-critical-point guarantees require RIP orders that grow with the search rank.Those landscape conditions can become more demanding under overparameterization and may impose substantially higher measurement requirements.Source: §I · p. 1, A. Global minima versus the low-rank… · p. 2

Main guarantee

  • Under the theorem’s RIP assumptions, every global minimizer satisfies the stated error bound whenever δ < δsharp(k/r⋆), with hidden constants depending only on δ and k/r⋆.The theorem assumes rank(X⋆) ≤ r⋆, A ∈ RIP(δ,k), and λ > 0.Source: §I · p. 1
  • The threshold is sharp: when δ ≥ δsharp(k/r⋆)+1/r⋆, counterexamples exist in which every global minimizer fails even in the noiseless case.For fixed t, this prevents uniformly relaxing the threshold as r⋆ grows.Source: §I · pp. 1–2
  • At λ ≍ ∥A*(ξ)∥op, the error bound is minimax optimal up to absolute constants under Gaussian noise.The constants in the bound do not depend on the search rank.Source: §I · p. 2

Consequences and scope

  • Making the rank cap inactive recovers the ordinary convex matrix LASSO, which inherits the same sharp threshold and error bound.This contrasts with prior penalized analyses that either used more conservative thresholds or obtained suboptimal error dependence.Source: §I · p. 2
  • The theorem guarantees recovery at a global minimizer for every search rank r ≥ r⋆, but does not provide an algorithm for finding that minimizer.Incremental lifting can certify global optimality, although its search rank may need to increase substantially; larger ranks also complicate the optimization landscape.Source: A. Global minima versus the low-rank… · p. 2

B. Extension to sparse-vector LASSO

The paper transfers its sharp rank-restricted matrix LASSO theory to sparsity-restricted vector LASSO, obtaining matching sufficiency and necessity thresholds and recovering the ordinary convex estimator when the sparsity cap is inactive.

Vector analogue

  • The vector theorem mirrors the matrix result by replacing target rank r⋆ with target sparsity s⋆ and using vector RIP.The proof first establishes the sparse-vector result, then transfers its singular-value geometry to matrices.Source: B. Extension to sparse-vector LASSO · pp. 2–3

Computational analogy

  • The sparse and matrix formulations are computationally analogous: active-set enlargement corresponds to rank-incremental lifting until the cap or full LASSO optimality conditions are reached.Fixing an active set leaves a small convex LASSO, just as fixing search rank leaves a low-dimensional factored problem.Source: B. Extension to sparse-vector LASSO · pp. 2–3

Sufficiency

  • If δ < δsharp(k/s⋆), every global minimizer of the sparsity-restricted vector LASSO satisfies the stated recovery bound, with constants depending only on δ and k/s⋆.The theorem assumes ∥x⋆∥0 ≤s⋆ and A ∈ rip(δ,k).Source: B. Extension to sparse-vector LASSO · p. 3

Necessity

  • If δ ≥δsharp(k/s⋆) + 1/s⋆, counterexamples exist in which every global minimizer fails to recover the ground truth, even when ξ = 0.The construction uses sparse targets with ∥x⋆∥0 ≤s⋆ and operators satisfying vector RIP at order k.Source: B. Extension to sparse-vector LASSO · p. 3

Convex specialization

  • Taking the search sparsity s=d removes the cap and yields the ordinary convex vector LASSO, for which the theorem gives a complete sharp-RIP guarantee.This parallels the rank-inactive specialization for the convex matrix LASSO.Source: B. Extension to sparse-vector LASSO · p. 3

Motivation

  • The penalized setting is harder than constrained recovery because LASSO solutions can have larger nuclear norm than the ground truth, so prior transfers sacrificed either sharpness or optimal error dependence.The paper’s result addresses this gap by attaining both the sharp threshold and the optimal error rate.Source: §II · pp. 3–4

A. Why the Standard Proof Loses Sharpness

The standard LASSO proof enlarges the head–tail relation multiplicatively, which raises the feedback gain and loses the sharp RIP threshold. Prior results also suffer from conservative thresholds or Euclidean-noise dependence.

  • The sharp threshold is determined by the single gain condition ρδ,t < 1, equivalent to δ < δsharp(t).The resulting error rate is O(λ√r⋆).Source: A. Why the Standard Proof Loses… · p. 4
  • The LASSO KKT condition controls the dual residual, but its nuclear-norm comparison can fail, yielding only an enlarged head–tail inequality.This enlargement is available under λ ≥ 2∥A*(ξ)∥op.Source: A. Why the Standard Proof Loses… · p. 4
  • 3ρδ,t < 1 replaces the sharp condition ρδ,t < 1 when the tail is bounded coarsely by 3H.The factor-three enlargement preserves the statistical rate but triples the feedback loop gain.Source: A. Why the Standard Proof Loses… · p. 4
  • Under Gaussian sensing, the Euclidean-noise calibration remains constant as m → ∞, whereas dual-noise calibration supports improved behavior with oversampling.Gaussian RIP holds with high probability once m ≳ δ^-2k(d1+d2).Source: B. Wang–Zhang–Wang: Sharp High-Order… · p. 5

III. LASSO RECOVERY GUARANTEES

The recovery proof introduces a head–tail defect to preserve the sharp feedback threshold for both vector and matrix LASSO. This yields explicit guarantees under δ < δsharp(t), with error controlled by the intrinsic rank or sparsity rather than the search size.

  • δ < δsharp(t) is equivalent to the contraction condition ρδ,t < 1 in the feedback argument.The margin 1−ρδ,t controls contraction, while τδ,t scales the measured-error contribution.Source: §III · p. 5
  • Under δ < δsharp(k/r⋆) and λ above the dual-noise level, every search rank r ≥ r⋆ satisfies the matrix LASSO recovery bound.The theorem’s constants depend on δ and t, while the guarantee applies at every admissible search rank.Source: §III · pp. 5–6
  • The vector theorem has the same sharp threshold for every sparsity level r ≥ r⋆.The matrix result follows by applying the vector argument to the singular values of the error.Source: §III · pp. 5–6
  • The proof decomposes error into a sparse head, diffuse tail, and a defect measuring violation of the exact head–tail relation.The head uses ℓ2 geometry, while the tail uses scale-normalized ℓ1 and ℓ∞ quantities.Source: §III · p. 5
  • The defect and best-r⋆ ordering control the tail without multiplying the head by a factor greater than one.This retains the sharp threshold that would be lost under the coarse bound T ≤ 3H.Source: §III · p. 6

A. Verification for the vector LASSO

The vector verification derives a global-optimality inequality from LASSO optimality, then transfers it to matrices through singular values. Matrix RIP becomes vector RIP along fixed singular directions, while norm and error identities preserve the conclusions.

  • Global optimality of the vector LASSO yields the basic perturbation inequality for σ = xλ,r − x⋆.The derivation expands the squared residual and applies the best-r⋆ ordering.Source: A. Verification for the vector LASSO · p. 7
  • The matrix proof reduces to the singular values of E = Xλ,r − X⋆, with ∥σ∥2 = ∥E∥F and ∥σ∥1 = ∥E∥nuc.The induced sensing matrix satisfies Aσ = A(E).Source: B. Verification for matrices · p. 7
  • The noise inner product is bounded by ∥A*(ξ)∥op∥E∥nuc, setting the dual-noise level λ0 = ∥A*(ξ)∥op.This is the matrix analogue of the vector dual-noise calibration.Source: B. Verification for matrices · p. 7
  • Matrix RIP transfers to vector RIP because rank(U diag(z)Vᵀ) equals ∥z∥0 and its Frobenius norm equals ∥z∥2.The transfer applies to vectors supported on at most k coordinates.Source: B. Verification for matrices · p. 7
  • Applying the vector result to singular values converts sparsity, ℓ1, and ℓ2 statements into rank, nuclear-norm, and Frobenius-norm statements.This completes the matrix theorem from the vector argument.Source: B. Verification for matrices · p. 7

IV. NECESSITY BY COUNTEREXAMPLES

The necessity construction produces adversarial matrix and vector instances above the proposed threshold, with unique global minimizers that remain far from the ground truth. A two-block identity-minus-rank-one design tunes the RIP constant while preserving optimality.

  • For every ε > 0, counterexamples exist at RIP constants δsharp(t) + ε, so the threshold cannot be uniformly improved.The construction applies at fixed rank ratio t = k/r⋆.Source: §IV · p. 7
  • The two-block construction places the ground truth and bad minimizer in orthogonal subspaces while annihilating their secant direction.Orthogonal directions supply subgradients establishing optimality, and α is tuned to achieve the target RIP constant.Source: §IV · p. 8
  • The bad minimizer is unique and remains separated from the ground truth, with ∥Xλ,r − X⋆∥F ≥ ∥X⋆∥F.The failure holds for every search rank r ≥ C(t)r⋆.Source: §IV · pp. 7–9
  • The identity-minus-rank-one map has an exactly computable RIP constant, enabling construction at the desired rank k.Lemma 25 characterizes RIP through the largest eigenvalue of the associated matrix.Source: §IV · p. 8
  • Integer rounding in the higher-order branch requires headroom δ − δsharp(t) ≥ 1/r⋆ to select the bad minimizer rank and tune α.Lemma 26 then guarantees the constructed map satisfies the required RIP condition.Source: §IV · pp. 8–9
  • The matrix counterexample transfers to the vector LASSO through a diagonal restriction preserving the recovery error.The vector instance inherits RIP and satisfies ∥xλ,r − x⋆∥2 = ∥Xλ,r − X⋆∥F.Source: §IV · pp. 7, 9

V. PROOF OF PROPOSITION 14

The proof establishes the sharp RIP condition by decomposing the error into a sparse head and diffuse tail, then designing sparse atomizations whose accumulated RIP errors remain controlled. It combines the established high-order mechanism with a new lower-order construction.

  • The proof splits the error into a sparse head and a diffuse tail, then represents the tail using sparse pieces.Source: §V · p. 9
  • RIP preserves sparse-piece norms and controls measured inner products between disjoint pieces, enabling comparison with the whole error.Source: §V · p. 9
  • Convex atomization replaces rigid tail blocks with sparse atoms whose diffuse scale reduces the conservatism caused by spiky initial blocks.Source: §V · p. 9
  • The lower-order branch 2 ≤ k < 4r⋆/3 requires a new idea because high-order atomization misses the sharp threshold, while k < r⋆ places the full head outside the RIP order.Source: §V · pp. 9–10
  • The proof uses head randomization and paired head-tail atoms to recover the sharp threshold for all k ≥ 2 and r⋆ ≥ 1.Source: §V · p. 10

A. High-order branch t ≥4/3

The high-order branch handles k ≥ 4r⋆/3 by separating large tail coordinates from a diffuse remainder, atomizing the remainder, and applying RIP to k-sparse combinations.

B. Low-order branch 0 < t < 4/3

The low-order branch uses randomized head pieces paired with complementary tail atoms, allowing disjoint k-sparse sums to exploit cancellations unavailable to high-order atomization.

2) Atomizing the tail:

Tail atomization converts a diffuse tail into sparse random vectors at prescribed sparsity levels while preserving its mean and controlling its second moment for the low-order construction.

3) RIP comparisons:

The RIP comparison constructs averaged quantities that couple randomized head and tail pieces, then compares them across the regimes t<1 and 1≤t<4/3. These comparisons establish the key low-order inequality underlying the recovery threshold.

Cancellation identities

  • The construction is designed around two cancellations, obtained by substituting the head and tail decompositions into the relevant second-moment expressions.The proof uses independence, uniform head means, tail means, and the relation σtail=σ−σhead to simplify the cross terms.Source: 3) RIP comparisons · pp. 11–12

Averaged quantities

  • X couples randomized head and tail pieces, while Y and Z reconstruct or augment head energy in the regimes t<1 and 1≤t<4/3.Every vector in X, Y, and Z is k-sparse because sampled head and tail supports are disjoint.Source: 3) RIP comparisons · p. 12

Regime-specific comparisons

  • For t<1, the proof compares X against Y; for 1≤t<4/3, it compares X against Z.The two comparisons use different constructions because Z exploits the additional k−r⋆ tail budget when t≥1.Source: 3) RIP comparisons · p. 12

RIP bounds

  • RIP lower and upper bounds are applied to the averaged quantities to produce the comparisons needed for the key low-order inequality.For t<1, the first norm receives lower RIP while the subtracted norm receives upper RIP; the same pattern is applied to X and Z for 1≤t<4/3.Source: 3) RIP comparisons · pp. 12–13

VI. CONCLUSION

The conclusion establishes sharp recovery thresholds for global minima of rank-restricted matrix and sparsity-restricted vector LASSO. It emphasizes that global-minimum guarantees depend on the ground-truth complexity rather than the search rank, when the search space contains the truth.

Main conclusion

  • The paper establishes the sharp recovery threshold δ<δsharp(t) for global minima of rank-restricted matrix LASSO and sparsity-restricted vector LASSO.Here t=k/r⋆ for matrix LASSO and t=k/s⋆ for vector LASSO.Source: §VI · p. 13

Proof strategy

  • The proof retains a defect term in the head-tail inequality, using an additive relation T≤H+D instead of a multiplicative relation T≤cH.This proof strategy is presented as the key idea for preserving the sharp threshold under penalized recovery.Source: §VI · p. 13

Search-rank dependence

  • At global minima, the sharp recovery threshold depends only on the ground-truth rank and is independent of the search rank when the search space contains the ground truth.The conclusion contrasts this with the greater landscape complexity and stronger assumptions that can arise when increasing the search rank for second-order critical-point analyses.Source: §VI · p. 13
Loading 2608.29018v1…