PaperlayerView exact revision on arXiv

Source-linked AI summary

Simultaneously Structured Models with Application to Sparse and Low-rank Matrices

Samet Oymak, Amin Jalali, Maryam Fazel, Yonina C. Eldar, Babak Hassibi

arXiv:1212.3753v3cs.ITmath.OC

TL;DR

The paper asks whether standard norms can efficiently recover signals with several structures at once. It develops a general framework for combined penalties and shows that, for sparse and low-rank matrices, nonconvex recovery can approach the degrees-of-freedom scale while convex combinations may require many more measurements.

  • Problem

    The paper studies how many measurements are needed to recover simultaneously structured models and whether combining norms for individual structures exploits their joint structure.

  • Method

    The paper analyzes multi-objective recovery using combinations of structure-inducing norms across broad measurement ensembles and compares convex relaxations with a nonconvex benchmark.

  • Results

    For simultaneously sparse and low-rank matrices, O((k1 + k2)r log n) measurements suffice nonconvexly, while the convex method requires at least Ω(rn) measurements.

  • Takeaways & Limitations

    Combining individual norms may perform no better than exploiting one structure, motivating new convex relaxations that capture simultaneous structure directly.

  • Takeaways & Limitations

    Constructing new atomic norms for simultaneous structures can be difficult to characterize and computationally intractable to minimize.

Abstract

from arXiv · show

The topic of recovery of a structured model given a small number of linear observations has been well-studied in recent years. Examples include recovering sparse or group-sparse vectors, low-rank matrices, and the sum of sparse and low-rank matrices, among others. In various applications in signal processing and machine learning, the model of interest is known to be structured in several ways at the same time, for example, a matrix that is simultaneously sparse and low-rank. Often norms that promote each individual structure are known, and allow for recovery using an order-wise optimal number of measurements (e.g., $\ell_1$ norm for sparsity, nuclear norm for matrix rank). Hence, it is reasonable to minimize a combination of such norms. We show that, surprisingly, if we use multi-objective optimization with these norms, then we can do no better, order-wise, than an algorithm that exploits only one of the present structures. This result suggests that to fully exploit the multiple structures, we need an entirely new convex relaxation, i.e. not one that is a function of the convex relaxations used for each structure. We then specialize our results to the case of sparse and low-rank matrices. We show that a nonconvex formulation of the problem can recover the model from very few measurements, which is on the order of the degrees of freedom of the matrix, whereas the convex problem obtained from a combination of the $\ell_1$ and nuclear norms requires many more measurements. This proves an order-wise gap between the performance of the convex and nonconvex recovery problems in this case. Our framework applies to arbitrary structure-inducing norms as well as to a wide range of measurement ensembles. This allows us to give performance bounds for problems such as sparse phase retrieval and low-rank tensor completion.

1 Introduction

The paper studies recovery of models with simultaneous structures and shows that combining standard structure-inducing norms can fail to exploit their joint degrees of freedom. For sparse and low-rank matrices, nonconvex recovery approaches the degrees-of-freedom scale, while convex combinations require substantially more measurements.

  • 1 Introduction: Simultaneously structured recovery seeks signals lying in the intersection of multiple structural sets, but the performance of combined regularizers lacks a general analysis.The paper addresses recovery using linear combinations of norms associated with individual structures.
  • 1 Introduction: O(rk) parameters describe a rank-r, k × k block-sparse matrix, motivating recovery from O(rk) measurements.Separate low-rank and block-sparse models require O(rn) and O(k^2) parameters, respectively.
  • 1 Introduction: Convex combinations of the ℓ1 and nuclear norms can require at least the measurement scale associated with only one structure.The paper states that multi-objective optimization with these norms cannot outperform an algorithm exploiting only one structure.
  • 1.1 Contributions: The framework covers general structure-inducing norms and measurement ensembles including Gaussian, subgaussian, quadratic, and matrix-completion measurements.It also incorporates convex cone constraints and analyzes how weights affect sample complexity.
  • 1 Introduction: O((k1 + k2)r log n) measurements suffice for the proposed nonconvex program, whereas the convex method cannot recover with fewer than Ω(rn) measurements.The matrix has O((k1 + k2)r) degrees of freedom, so the nonconvex method is only logarithmically suboptimal in this setting.
  • 1.1 Contributions: The paper identifies a gap between convex and nonconvex recovery for simultaneously sparse and low-rank matrices.The nonconvex program is used as a theoretical benchmark, while the convex relaxation is tractable but can perform poorly.

2 Problem Setup

The setup formalizes simultaneously structured signals, norm-based multi-objective recovery, and Pareto-optimal recoverability. It also introduces correlation and κ to connect norm geometry with model complexity.

  • Norm geometry: Correlation ρ(x,S) measures the minimum absolute-valued correlation between a nonzero vector x and elements of a set S.For norm subdifferentials, the associated correlation can be bounded using the local Lipschitz constant and κ.
  • Norm geometry: κ measures alignment between a vector and a norm subdifferential and is associated with model complexity for norms of interest.Geometrically, κ is represented using the Euclidean norm of a closest point on a scaled norm ball and the norm of x0.
  • Simultaneously structured models: A simultaneously structured model has several low-dimensional structures, each promoted by its own structure-inducing norm.Examples include sparsity, group sparsity, and low rank, promoted by ℓ1, ℓ1,2, and nuclear norms.
  • Convex recovery program: Recovery seeks a feasible signal whose vector of individual norm values is Pareto optimal among points satisfying the measurements and side information.The achievable norm set is replaced by a convex upper set with the same Pareto-optimal points.
  • Convex recovery program: Weighted sums of the individual norms recover Pareto-optimal points under convexity and strong duality, with coefficients determined by supporting hyperplanes.The scalar objective is a convex, coordinatewise non-decreasing function of the structure-inducing norms.
  • Convex recovery program: The paper seeks lower bounds on the number of measurements required for recoverability and notes that new atomic norms for simultaneous structures may be computationally intractable.Figure 3 links the measurement threshold to whether x0 lies on the Pareto-optimal front.

3 Main Results: Theorem Statements

The paper derives general lower bounds for recovering simultaneously structured signals with combinations of structure-inducing norms, then compares convex and nonconvex recovery for sparse and low-rank matrices.

  • General results: The framework lower-bounds measurements needed for simultaneous structures using geometric properties of the individual norms.The analysis separates signal/subdifferential geometry from measurement-map behavior.
  • General results: For Gaussian measurements, below m_low, the signal is not a minimizer of any considered convex recovery program with high probability.The result applies to the whole class of weighted multi-objective programs rather than one fixed combination.
  • General results: The required measurements are effectively determined by one dominant structure, even when the signal satisfies multiple structures.The lower bound is governed by κ_min n, while the simultaneous model may have substantially fewer degrees of freedom.
  • Sparse and low-rank matrices: Nonconvex programs require nearly the degrees-of-freedom count up to logarithmic factors, whereas the corresponding convex programs require significantly more measurements.The comparison establishes an order-wise performance gap between convex and nonconvex recovery.
  • Sparse and low-rank matrices: For the sparse-and-low-rank setting, the convex lower bounds remain high even after adding a cone constraint such as positive semidefiniteness.The paper also reports matching upper and lower bounds up to logarithmic factors for the combined convex cost in a specialized case.

4 Measurement ensembles

The paper analyzes several measurement ensembles, including sub-gaussian, entry-sampling, and quadratic measurements, with probabilistic bounds and assumptions tailored to each setting.

  • Measurement models: The framework covers matrices with sub-gaussian rows, subsampled standard-basis measurements for matrix completion, and quadratic measurements from phase retrieval.These ensembles are treated as representative applications of the general measurement analysis.
  • Sub-gaussian measurements: For sub-gaussian measurements, rows are either isotropic with fixed ℓ2 norm or have independent zero-mean unit-variance sub-gaussian entries.Under these assumptions, Proposition 4.1 provides probabilistic conditioning bounds when m is at most a constant multiple of n.
  • Entry sampling: Duplicate rows in uniformly sampled standard-basis measurements can be discarded without changing the null space or recoverability.After duplicates are removed, the resulting matrix has σ_min equal to 1.
  • Entry sampling: Entry-sampling failure bounds require the true signal to be incoherent with the standard basis, characterized through its ℓ∞ norm.The stated incoherence range lies between 1/√n and 1.
  • Quadratic measurements: Quadratic measurements are linearized by mapping a to X0 = aaT and each measurement vector v to V = vvT.This transformation permits the general lower-bound theorem to be applied to phase-retrieval measurements.
  • Quadratic measurements: For sparse phase retrieval, combined ℓ1 and nuclear-norm recovery fails with high probability below a measurement threshold involving d log d and the signal-dependent norm terms.The comparison passage notes that the resulting lower bound remains applicable when the signal is sparse.

5 Upper bounds

The section bounds recovery by simultaneous optimization of multiple structure-inducing norms through distances to dilated subdifferentials. For Gaussian measurements, the resulting complexity is controlled by combinations of the individual norm complexities, including for sparse and low-rank matrices.

  • The upper bound is obtained by choosing dilation parameters for the individual norms and relating them to their separate sample complexities.
  • The phase transition for joint optimization is related to the individual subdifferentials of the combined penalty.
  • For Gaussian measurements, recovery succeeds when the number of measurements exceeds a squared upper-bound expression involving the dilated-subdifferential distance.The success probability is at least 1 − 2 exp(−t^2…).
  • For sparse and low-rank matrices, the convex-combination bounds combine the individual sparsity and rank contributions rather than yielding degrees-of-freedom scaling.
  • The specialized analysis applies the Gaussian upper bound to sparse-and-low-rank matrices using existing complexity estimates for the ℓ1 and nuclear norms.

6 General Simultaneously Structured Model Recovery

This section develops general lower-bound and optimality tools for recovery programs combining multiple norms. It introduces decomposable norms and shows that failure of the best coordinatewise objective implies failure for every monotone combination in the class.

  • The recovery framework considers vectors with multiple norm-associated structures, cone constraints, and lower bounds on the measurements needed for recovery.
  • If the best coordinatewise objective fails to recover x0, every monotone combination of the individual norms also fails.
  • Any subgradient of a convex function of multiple norms is a nonnegative conic combination of subgradients of the individual norms.
  • The lower bounds use subspace projections, correlations, and measurement singular values to establish deterministic and probabilistic recovery failure conditions.
  • For sparse vectors, choosing the sign-vector subspace yields an Ω(k) measurement lower bound, matching the minimum needed to estimate a k-sparse vector.
  • Decomposable norms: Decomposable norms represent their subdifferentials using a support subspace and a sign vector, with ℓ1, ℓ1,2, and nuclear norms included.

7 Proofs for Section 3.2

The proofs specialize the general framework to sparse-and-low-rank matrices, deriving convex lower bounds and nonconvex recovery guarantees. A Hadamard-based construction supplies matrices whose sparsity and low-rank norm parameters are simultaneously large.

  • Convex recovery: The convex recovery results for sparse-and-low-rank models follow by applying the general lower-bound theorems to decomposable norms and model-specific supports.
  • Nonconvex recovery: A subgaussian null-space lemma controls matrices supported on an s1 × s2 submatrix with rank at most q.
  • Nonconvex recovery: The nonconvex proofs ensure uniqueness by excluding nonzero null-space matrices from structured matrix classes.
  • Nonconvex recovery: Positive semidefinite symmetry constraints can only reduce the measurements required relative to the corresponding unconstrained nonconvex problem.
  • Large norm parameters: Hadamard matrices construct sparse-and-low-rank examples with simultaneously large ℓ1, ℓ1,2, and nuclear-norm parameters.
  • Large norm parameters: For the constructed matrix, the squared ℓ1,2 quantities satisfy ∥X̄0∥^2_1,2 ≥ k2^2 and ∥X̄T̄0∥^2_1,2 = k1.

8 Numerical Experiments

The experiments test predicted measurement-scaling bounds for sparse-and-low-rank recovery and compare weighted maximum, weighted-sum, and single-structure penalties. The observed phase transitions and failure behavior broadly follow the theoretical predictions.

  • The experiments evaluate weighted maximum and weighted-sum penalties using repeated recovery trials over grids of measurement and matrix dimensions.
  • Block sparsity: For rank-1 PSD matrices with block sparsity, recovery measurements scale linearly with d under the ℓ1,2-based maximum penalty.
  • Entrywise sparsity: Entrywise ℓ1 recovery exhibits the predicted Ω(min{k2, d}) failure boundary, growing with d before saturating when k2 dominates.
  • Weighted sums: Weighted-sum recovery with λ = 0.20 and λ = 0.35 performs comparably to the weighted maximum penalty in the tested rank-1 PSD setting.
  • Failure behavior: When recovery fails, normalized errors above 10^-4 and 0.05 produce nearly overlapping failure curves, indicating typically large errors.
  • Scaling with dimension: For large d, the required measurements are expected to grow logarithmically because sparsity becomes the dominant structure.
  • Method comparison: The best-performing method requires at least half as many measurements as the minimum of the two single-structure alternatives across sparsity regimes.

9 Discussion

The discussion concludes that combined norm penalties are limited relative to degrees-of-freedom expectations and motivates new atoms, tighter bounds, and recovery-error analysis. It also connects the framework to sparse PCA and notes practical solvability of convex formulations.

  • Combined norm penalties require more generic measurements than expected from the desired object's degrees of freedom.The lower bounds imply performance cannot significantly exceed that of the best individual norm.
  • Recovery failures in Figure 8 produce significant errors, with nearly coincident curves for normalized-error thresholds 10^-4 and 0.05.The discussion proposes lower bounds on recovery error as a function of the number of problem parameters.
  • New atoms that capture multiple structures could yield stronger convex penalties, but their convex hulls may be difficult to characterize or compute.The discussion cites the square norm and (k, q)-trace norm as examples of related developments.
  • The sparse and low-rank matrix optimization problems discussed in Theorem 3.3 can be expressed as semidefinite programs and solved by standard solvers.
  • For sparse signals in time and frequency, the mixed approach can achieve a logarithmic improvement over individual functions when k1 ≈ k2.The cited result requires as little as max{k1, k2} log log n under mild assumptions.
  • Sparse PCA can be formulated using a rank-1, positive semidefinite matrix that is also row- and column-sparse.This differs from the paper's recovery setting because it does not use m random measurements of the matrix.

B.1 Relevant notation for the proofs

The proof notation identifies the support subspaces and singular-value decomposition of the simultaneously structured matrix.

  • Sc and Sr denote the indexes of nonzero columns and rows, while Sc and Sr denote vector subspaces supported on those indexes.
  • The notation separates the matrix's row, column, and rank-related structure through their corresponding support and singular-vector spaces.
  • The matrix X0 is represented as X0 = UΣVT, with U and V supported on the column and row index sets.

B.2 Proof of Lemma 7.1

The proof places the constructed matrices associated with row, column, and rank structure in a common intersection and establishes nonnegative pairwise inner products.

  • Ec is obtained by right-multiplying X0 by a nonnegative diagonal scaling matrix and remains in the range space of X0.
  • Er is analogously obtained by left-multiplying X0 by a nonnegative diagonal matrix and lies in T⋆.
  • E⋆, Ec, and Er all lie in the intersection Tc ∩ Tr ∩ T⋆.
  • The pairwise inner products of Er, Ec, and E⋆ are nonnegative.

B.3 Results on the positive semidefinite constraint

The positive semidefinite analysis uses orthogonality and cone geometry to characterize the relevant subspaces and establish containment in an orthogonal complement.

  • For a positive semidefinite X, orthogonality ⟨Y, X⟩ = 0 implies UᵀY = 0, where U contains X's rank-associated eigenvectors.
  • When the support sets coincide, the analysis specializes to Sc = Sr, Tc = Tr, and k1 = k2 = k.
  • The proof shows that span(Y) is contained in S⊥ under the stated positive semidefinite and orthogonality conditions.
  • The argument also establishes a corresponding norm relation for Ec, with an analogous result for Er.

C Results on non-convex recovery

This section establishes measurement and covering-number tools for cones of structured matrices, then applies them to show that the measurement null space avoids the target cone under sufficient measurements.

  • Sub-gaussian measurement operators provide uniform control over the measurement norm on unit-Frobenius-norm matrices.The argument uses zero-mean, unit-variance measurements and concentration for sums of sub-exponential variables.
  • The unit-Frobenius-norm sphere is the normalization used for the covering and null-space arguments.For consequent lemmas, Sd1×d2 denotes the unit Frobenius norm sphere.
  • If a cone’s unit-sphere intersection has covering number η(ε), m ≥ c1 log η(1/4) measurements ensure null-space avoidance with probability 1 − 2 exp(−c2m).The result applies to measurement operators with i.i.d. zero-mean isotropic sub-gaussian rows.
  • Rank-at-most-r matrices have covering entropy bounded by C(d1 + d2)r, supplying the low-rank component of the measurement bound.The covering is constructed for the intersection of the unit-Frobenius-norm sphere with the rank-constrained set.
  • The same covering-number strategy is extended to matrices that are simultaneously low-rank and sparse.The section explicitly applies the low-rank covering lemma to the simultaneously structured class.

C.1 Proof of Lemma 7.2

The proof bounds the covering number of simultaneously sparse and low-rank matrices by covering each admissible submatrix and combining those covers across supports.

  • The proof invokes Lemma C.2 to convert a 1/4-covering number N into the measurement condition m ≥ c1 log N.The remaining task is to bound N for the simultaneously structured matrix set.
  • Each individual s1 × s2 submatrix is covered using the low-rank covering result.For a fixed submatrix, the 1/4-covering number is bounded by C(s1 + s2)q.
  • The covers for all distinct submatrices are combined by taking their union.The proof then applies logarithmic bounds to the resulting collection to obtain the desired result.
Loading 1212.3753v3…