PaperlayerView exact revision on arXiv

Source-linked AI summary

ADMiRA: Atomic Decomposition for Minimum Rank Approximation

Kiryung Lee, Yoram Bresler

arXiv:0905.0044v2math.NAcs.IT

TL;DR

The paper addresses recovery of low-rank matrices from compressed measurements, where rank minimization is computationally difficult. It introduces ADMiRA, an atomic-decomposition generalization of CoSaMP, and reports guarantees for noisy approximately low-rank recovery plus competitive matrix-completion performance despite absent R-RIP.

  • Problem

    Rank minimization for recovering low-rank matrices is NP-hard, while convex nuclear norm formulations use semidefinite programs.

  • Method

    ADMiRA uses an atomic decomposition to generalize CoSaMP's greedy sparse-recovery strategy to rank-r matrix approximation.

  • Results

    ADMiRA provides a performance guarantee for approximately low-rank matrices with noisy measurements and is effective for matrix completion even without R-RIP.

  • Takeaways & Limitations

    ADMiRA offers an efficient approach to large-scale rank minimization, with matrix-completion computations dominated by operations linear in the number of measurements.

Abstract

from arXiv · show

We address the inverse problem that arises in compressed sensing of a low-rank matrix. Our approach is to pose the inverse problem as an approximation problem with a specified target rank of the solution. A simple search over the target rank then provides the minimum rank solution satisfying a prescribed data approximation bound. We propose an atomic decomposition that provides an analogy between parsimonious representations of a sparse vector and a low-rank matrix. Efficient greedy algorithms to solve the inverse problem for the vector case are extended to the matrix case through this atomic decomposition. In particular, we propose an efficient and guaranteed algorithm named ADMiRA that extends CoSaMP, its analogue for the vector case. The performance guarantee is given in terms of the rank-restricted isometry property and bounds both the number of iterations and the error in the approximate solution for the general case where the solution is approximately low-rank and the measurements are noisy. With a sparse measurement operator such as the one arising in the matrix completion problem, the computation in ADMiRA is linear in the number of measurements. The numerical experiments for the matrix completion problem show that, although the measurement operator in this case does not satisfy the rank-restricted isometry property, ADMiRA is a competitive algorithm for matrix completion.

I. INTRODUCTION

The paper formulates low-rank matrix recovery as minimum-rank approximation and develops ADMiRA, a guaranteed greedy algorithm extending CoSaMP through an atomic decomposition.

  • Low-rank matrix compressed sensing reconstructs X0 from linear measurements while using rank as the matrix analogue of sparsity.
  • Rank minimization is NP-hard, motivating nuclear norm minimization as a convex surrogate, though the resulting problem is a semidefinite program.
  • Minimum rank approximation handles noiseless, noisy, and approximately low-rank settings in one formulation.
  • When the minimum rank is unknown, incremental search costs at most a factor r, while bisection reduces this factor to log r when an upper bound is available.
  • ADMiRA generalizes CoSaMP to matrices using atomic decomposition, with least squares and truncated singular value decompositions as its core computations.
  • For matrix completion, ADMiRA has no R-RIP guarantee because the measurement operator lacks R-RIP, but experiments report better performance than SVT.

III. ALGORITHM

ADMiRA iteratively selects atoms that approximate the current residual, refines them into a rank-r solution, and relies on R-RIP behavior for its selection rationale.

  • ADMiRA refines a rank-r atom set and approximate solution by repeatedly targeting information not explained by the previous iterate.
  • The algorithm selects 2r leading principal components of A*(b − A X̂) as a proxy for the residual when A acts nearly isometrically on low-rank matrices.
  • The selected atoms are merged with the current set and refined back to r atoms to approximate X0.
  • The R-RIP assumption means A approximately preserves norms of matrices whose rank is at most r.

B. Performance Guarantee

ADMiRA provides CoSaMP-like performance guarantees under the rank-restricted isometry property, with explicit bounds on convergence, approximation error, and iteration count. These guarantees account for approximate low-rank structure and noisy measurements, while matrix completion remains outside the formal guarantee.

  • Under the R-RIP, ADMiRA has a performance guarantee analogous to CoSaMP.The guarantee relies on the operator satisfying the rank-restricted isometry property.
  • The unrecoverable energy combines the best rank-r approximation error with the measurement-noise norm.Its approximation component is optimal by the Eckart-Young-Mirsky theorem.
  • Theorem 4.1 gives geometric convergence, with ||X0 − X̂k||F <= 2^-k ||X0||F + 16ε for every k >= 0.The unrecoverable energy ε captures approximation error and measurement noise.
  • After at most 6(r + 1) iterations, ADMiRA produces a rank-r approximation satisfying the stated error guarantee.The bound is uniform in the number of iterations, while ε denotes unrecoverable energy.
  • For noiseless measurements and r >= rank(X0), ADMiRA recovers X0 exactly under its assumptions.An incremental search can assign an appropriate target rank r.

VI. PROOF OF THEOREM 4.1

The proof establishes geometric error contraction for ADMiRA under the rank-restricted isometry property, while controlling noise and rank-truncation effects.

  • Theorem 6.1: Theorem 6.1 gives an iteration recursion for ADMiRA’s estimate under the rank-restricted isometry property.The proof generalizes the performance-guarantee strategy of CoSaMP to low-rank matrices.
  • Error recursion: The resulting recursion is ∥X0 − bXk+1∥F ≤ 0.5∥X0 − bXk∥F + 6.5∥ν∥2.The update bXk+1 = eXr completes each iteration after rank truncation.
  • Error recursion: After k iterations, the error satisfies ∥X0 − bXk∥F ≤ 2^-k∥X0∥F + 13∥ν∥2.The bound combines geometric decay of the initial error with a noise-dependent floor.
  • Atom selection: The atom-selection step captures 94% of the energy not captured by the previous estimate, with additive measurement noise bounded by a small constant.This guarantees substantial progress in each iteration.
  • Least squares: The least-squares step performs almost as well as recovery with an identity measurement operator, except for components outside the augmented atom span.The span restriction makes those orthogonal components unrecoverable in that step.
  • Rank truncation: Reducing the augmented estimate from rank 3r to rank r increases the approximation error by at most a factor of 2.The rank-r estimate is formed as the best rank-r approximation of the augmented estimate.

B. General Matrix Case

The general-case analysis converts approximation error into effective measurement noise and bounds ADMiRA’s accuracy and iteration count for approximately low-rank matrices.

  • Approximately low-rank case: Modeling error from approximating X0 by its best rank-r matrix is converted into equivalent additive measurement noise.For arbitrary X0, b = AX0,r + eν with eν = A(X0 − X0,r) + ν.
  • Accuracy guarantee: The general-case recursion combines contraction of the rank-r approximation error with terms for unrecoverable energy and effective noise.The proof applies the exactly low-rank guarantee to X0,r and then uses the triangle inequality.
  • Iteration bounds: The iteration bound is uniform, while matrices with clustered singular values can converge faster.The analysis depends on the singular-value distribution rather than the singular vectors.
  • Matrix profile: The profile of a matrix counts occupied logarithmic singular-value bands and satisfies profile(X) ≤ rank(X).Atomic bands group normalized singular values into one-octave intervals.
  • Exactly low-rank case: For exactly rank-r matrices, ADMiRA reaches the stated approximation guarantee within a bounded number of iterations.The bound is expressed using the profile of X0.
  • Approximately low-rank case: The analysis extends the iteration guarantee to arbitrary matrices using profile(X0,r) and the unrecoverable energy.The unrecoverable energy quantifies the portion not represented by the rank-r approximation.
  • Iteration bounds: The approximation error is achieved within at most 6(r + 1) iterations for any matrix X0.A smaller profile(X0,r) can yield faster convergence, roughly proportional to the number of logarithmic singular-value clusters.

VIII. IMPLEMENTATION AND SCALABILITY

ADMiRA scales through factorized matrix representations and efficient linear-algebra primitives, with especially low costs for sparse measurement operators. Matrix-completion experiments report strong recovery and competitive performance against SVT, while the theory does not apply because matrix completion lacks R-RIP.

  • Computational structure: Each ADMiRA iteration uses applications of A and A∗, singular value decompositions, and least-squares solves while retaining most variables in factorized form.Factorized representations reduce the cost of low-rank approximation relative to direct operations on full matrices.
  • Computational structure: For an extremely sparse operator, computing A bX and A∗y costs O(pr) and O(p), respectively.This setting includes matrix completion, where the atomic factors have O(1) nonzeros.
  • Matrix-completion experiments: For n = 500, Fig. 1 suggests p/dr ⩾20 is needed, with both SNRrecon and iteration count improving as p/dr increases.Here dr = r(n + m −r) is the number of degrees of freedom in a real rank-r matrix.
  • Matrix-completion experiments: At p = 10⌈n1.2r log10 n⌉, ADMiRA provides nearly perfect recovery of random matrices, although iteration counts increase with n.The reported completion threshold follows the cited sampling prescription for n × n rank-r matrices.
  • Matrix-completion experiments: ADMiRA slightly outperforms SVT with less computation in most tested examples, while one ADMiRA iteration costs roughly twice one SVT iteration.The phase-transition experiment also reports better performance for ADMiRA than SVT.
  • Scope of guarantees: The R-RIP guarantee does not apply to matrix completion, although experiments show ADMiRA is effective in that setting.The paper therefore presents matrix-completion performance empirically rather than as a consequence of the theorem.

APPENDIX

The appendix develops operator and projection arguments used to relate rank-restricted measurements to subspaces generated by matrix atoms. These steps establish norm bounds for projected components under R-RIP.

  • R-RIP arguments: The rank-restricted isometry constant δr(A) is monotone nondecreasing in r.This follows because the feasible rank-r sets expand as r increases, while the associated extremal quantities move monotonically.
  • R-RIP arguments: For a subspace generated by at most r atoms, the associated isometry LΦ preserves coefficient and Frobenius norms.The passage explicitly invokes rank at most r and the R-RIP condition for this preservation.
  • R-RIP arguments: The operator norm of ALΦ and its adjoint is bounded using 1 + δr(A).This bound transfers the R-RIP control to the atom-generated subspace.
  • Projection arguments: For commuting projections P and PΨ, their product projects onto the intersection of their ranges and can be represented through an isometry LΦ.The intersection subspace remains rank-controlled when it lies inside the span generated by at most r atoms.
  • Projection arguments: Every projected matrix PPΨX can be represented as LΦα, and the R-RIP yields a lower bound proportional to (1 −δr(A))∥PPΨX∥F.The coefficient norm equals the Frobenius norm because LΦ is an isometry.

E. Proof of Proposition 5.7

The proof decomposes a matrix through its singular values into normalized rank-r components, showing that the relevant unit ball lies in the convex hull generated by rank-r atoms.

  • Proof setup: The proof begins with unit-Frobenius-norm, orthogonal matrices and uses rank subadditivity for their unit-modulus combinations.The argument considers α with |α| = 1 and specializes to α = ±1, ±i.
  • Convex-body argument: The unit ball in a subspace spanned by atoms is characterized through the convex hull of its generating set.The proof then introduces a second convex body and compares the associated operator norms.
  • Singular-value decomposition: A matrix in the relevant convex body is decomposed using its singular value decomposition into blocks controlled by groups of at most r singular components.The construction orders singular values and sets σk = 0 beyond the matrix rank.
  • Convex-body argument: Each normalized block belongs to the rank-r atom set, so the original matrix is a convex combination of those blocks and lies in the convex hull.The proof uses rank(Yj) ⩽r and ∥Yj∥F = 1 for every constructed block.

H. Proof of Lemma 6.2

The proof bounds the proxy-selection error from above and the refinement quantity from below using rank-controlled atom spans, projection decompositions, and R-RIP constants.

  • Upper bound: The error X0 − bX spans at most 2r atoms, enabling the proxy-selection rule to control its projected correlation.The proof defines Φ from the error and invokes the selection rule for Ψ′.
  • Projection decomposition: The intersection span Υ allows PΦ and PΨ′ to be decomposed into mutually orthogonal projection components.This decomposition supports the subsequent Pythagorean argument.
  • Bounding inequality (30): The proof separately derives upper bounds for the right-hand side and lower bounds for the left-hand side of inequality (30).These bounds are assembled using prior propositions and constraints on the projection spans.
  • Bounding inequality (30): The lower-bound derivation combines projection estimates and maximization over PΥ under its stated constraint.The resulting inequality is then combined with the earlier upper bound.
  • Final constants: Substituting δ2r(A) ⩽δ4r(A) ⩽0.04 produces the constants in the final inequality.The numerical R-RIP bound enters only at the final constant substitution.

I. Proof of Lemma 6.3

The proof derives the minimizer and bounds its error using triangle inequalities, rank subadditivity, and the R-RIP condition. The argument closes when δ3r(A) is bounded by 0.04.

  • The minimizer in (16) is introduced and its error is decomposed into terms bounded separately.
  • The proof uses triangle-inequality bounds and the best rank-r approximation property to control approximation error.
  • The final inequality follows from the R-RIP of A.
  • Rank subadditivity establishes the relevant rank bound, with eΨX0) ⩽4r.
  • δ3r(A) ⩽δ4r(A) ⩽0.04 completes the proof.

K. Proof of Lemma 6.5

The proof shows that generalized correlation maximization identifies atomic bands iteratively. Under the stated conditions, all bands are identified within a bounded number of iterations, yielding the claimed guarantees.

  • Atomic-band identification: The generalized correlation maximization rule selects Ψ′ in the k-th iteration, with bΨk chosen as a subset of eΨk.
  • Guarantee: For all k ∈Z+, the stated iterative guarantee follows from Lemmas 6.4 and 6.5 and the subsequent case analysis.
  • Iteration bound: Jensen’s inequality is used to bound the total iterations through the number of nonempty atomic bands and the profile t.
  • Atomic-band identification: Claim 1 establishes that each target band Bj is contained in bΨk.
  • Atomic-band identification: Once Bj is identified, the identification condition implies that every earlier band Bℓ, for ℓ⩽j, is also identified.
  • Iteration bound: After the bounded number of additional iterations specified in the proof, Bj is identified.

N. Proof of Theorem 7.3

The theorem analyzes an arbitrary matrix through its best rank-r approximation and bounds the reconstruction error after a finite number of iterations. The resulting error depends on measurement noise and the matrix’s rank-r approximation error.

  • If the stopping condition does not hold during the first K iterations, the lemmas imply that all atoms in atoms(X0) are identified by iteration K.
  • The assumption that the stopping condition never holds is contradicted, so some k⩽K satisfies condition (19).
  • For arbitrary X0, the measurement is rewritten as b = AX0,r + eν using the profile t = profile(X0,r).
  • After the stated iteration bound, the approximation error satisfies ∥X0 −b X∥F ⩽ 15 ∥eν∥2 + ∥X0 −X0,r∥F.
Loading 0905.0044v2…