Source-linked AI summary
Low-rank matrix recovery landscapes beyond RIP with application to rank-one measurements
Andrew D. McRae
TL;DR
Low-rank recovery through a factored formulation is attractive computationally, but nonconvexity can leave algorithms at spurious local optima. This paper analyzes the factored matrix LASSO using a weaker tangent-space upper-isometry condition, and shows that its second-order critical points satisfy a statistically meaningful recovery bound.
Problem
The factored low-rank least-squares problem can have spurious local optima, so its critical points need guarantees that they yield good estimates.
Source: §1 · p. 2Method
The paper analyzes the landscape of a factored low-rank formulation of matrix LASSO, replacing global upper isometry with an upper-isometry condition on the ground-truth tangent space.
Source: §1 · p. 2Results
Every second-order critical point satisfies a recovery error bound that is optimal within constants and reflects measurement error and the rank and regularization parameters.
Source: §1 · p. 3, §1.1 · p. 4Takeaways & Limitations
A benign landscape means local optima yield good statistical estimates, supporting the use of the factored formulation as a scalable alternative to matrix LASSO.
Source: §1 · p. 2The failure-probability bound is O(1/D) and is the bottleneck for the paper’s probability bounds.
Source: §3.3.2 · p. 18
Abstract
from arXiv · showhide
We study the problem of low-rank matrix recovery from linear measurements via the global nonconvex landscape of a low-rank factored formulation of the matrix LASSO (nuclear-norm--regularized least-squares). If the landscape is benign, that is, has no bad local optima, then practical and scalable algorithms can compute good statistical estimates. Previous state-of-the-art landscape guarantees have typically assumed that the linear measurement operator has the restricted isometry property, that is, the operator is approximately an isometry over all low-rank matrices. This is an unrealistic assumption for many applications; in particular, when the individual measurement matrices are themselves low-rank, we typically have poor upper isometry constants. To overcome this, we establish new guarantees of a benign landscape under a weaker isometry condition: rather than requiring upper isometry over all low-rank matrices, we only require it over the linear low-rank tangent space to the low-rank ground truth matrix. To illustrate the utility of this result, we apply it to the problem of matrix recovery from random rank-one linear measurements; via high-probability concentration bounds on the random measurement operator, we prove a novel landscape guarantee with statistically near-optimal sample complexity and recovery error.
1 Introduction and main results
The paper studies whether the factored low-rank recovery problem has a benign optimization landscape, using a weaker upper-isometry requirement than RIP. It applies this framework to random rank-one measurements and gives a landscape guarantee under a near-optimal sample-size condition.
1 Introduction and main results
- The factored problem is a computationally scalable alternative to matrix LASSO, but its nonconvexity can create spurious local optima, motivating guarantees that critical points yield good estimates.With λ = 0, the formulation is a smooth reparameterization of rank-constrained least squares.Source: §1 · p. 2
1.1 Main deterministic landscape guarantee
- The deterministic guarantee replaces RIP’s broad upper-isometry requirement with upper isometry on the tangent space to M*, while retaining an error bound comparable to the RIP-based bound and optimal within constants.The theorem also requires restricted lower isometry on the error matrices.Source: §1.1 · pp. 4–5
1.2 Application to random rank-1 measurements
- For independent isotropic sub-Gaussian rank-one measurements, the theorem guarantees recovery bounds at second-order critical points when the sample size is about r*(d1 + d2) log(d1 + d2), within a logarithmic factor of optimal when r ≈ r*.The theorem’s probability guarantee and recovery bound are stated for every second-order critical point under the specified sample condition.Source: §1.2 · pp. 5–6
2 Deterministic proof
The proof normalizes second-order critical points to balanced factors, derives an inequality that permits upper isometry only on the ground-truth tangent space, and combines these tools to prove the landscape guarantee.
2 Deterministic proof
- The deterministic proof also applies to symmetric and complex cases, with the stated notation adjustments.Source: §2 · p. 6
2.1 Reduction to the balanced case
- Any balanced factorization of the matrix at a second-order critical point is also a second-order critical point, allowing the proof to assume balanced factors.Source: §2.1 · p. 7
2.2 Key inequality from second-order criticality
- The core inequality permits the proof to require upper isometry only on the ground-truth tangent space, and the result also holds in the symmetric case.Source: §2.2 · p. 8
- The authors leave unclear whether the key inequality extends to non-quadratic objective functions.Source: §2.2 · p. 8
2.3 A norm inequality
- The norm-inequality result also holds in the symmetric specialization with U = V and U* = V*.Source: §2.3 · p. 10
2.4 Putting it together
- Combining the preceding inequalities with A's isometry assumptions completes the proof of Theorem 1.1.Source: §2.4 · pp. 12–13
3 Matrix sensing with random measurements
This section analyzes matrix sensing with random measurements by first establishing a general guarantee, then applying it to rank-one measurements. The proof combines restricted lower concentration with upper isometry on the ground-truth tangent space.
3.1 General random measurements
- Under isotropy, a moment condition, and boundedness on the tangent space, Theorem 3.1 gives a guarantee for every second-order critical point when its sample-size condition holds.The theorem covers asymmetric and symmetric measurement models.Source: §3.1 · pp. 13–14
3.2 Proof for rank-1 measurements
- For rank-one measurements A = ab⊤, the proof verifies the general theorem’s assumptions, using independent isotropic vectors to establish isotropy.The argument also uses concentration bounds to establish the moment and tangent-space conditions.Source: §3.2 · pp. 14–15
3.3 Proof of general result
- The general theorem follows from the deterministic result and two concentration lemmas, applied with rank parameter k = r + r∗.The lemmas establish restricted lower concentration and upper concentration on the tangent space.Source: §3.3 · pp. 15–16
3.3.1 Restricted lower isometry
- A covering argument extends the lower concentration bound from fixed matrices to all matrices of rank at most k.The proof uses a Frobenius-norm covering and a union bound.Source: §3.3 · p. 15, §3.3.1 · p. 17
3.3.2 Tangent space upper isometry
- The upper concentration lemma controls the measurement operator restricted to the tangent space, yielding the required tangent-space upper isometry.The proof applies the concentration result to the projected measurements; the failure-probability bound is identified as a bottleneck.Source: §3.3.2 · pp. 17–18