PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning

Fei Wen, Lei Chu, Peilin Liu, Robert C. Qiu

arXiv:1808.05403v3cs.ITcs.LGeess.SPstat.ML

TL;DR

Sparse and low-rank recovery commonly uses tractable convex penalties, but these can be biased and less statistically efficient than nonconvex alternatives. This survey synthesizes nonconvex regularization across major applications, develops the role of proximity operators and convergence, and concludes that penalty choice should depend on sparsity, rank structure, and noise.

  • Problem

    Convex ℓ1 and nuclear-norm penalties are tractable but can produce biased estimates, motivating nonconvex regularization for sparse and low-rank recovery.

  • Method

    The paper surveys nonconvex regularization across applications and reviews penalty selection, proximity operators, and convergence of related algorithms.

  • Results

    The survey concludes that penalty selection should depend on sparsity or rank structure and noise, with aggressive thresholding favored for strictly sparse, low-noise settings.

  • Takeaways & Limitations

    Convex and nonconvex models require careful deliberation because nonconvex methods may offer limited gains while incurring slower convergence and greater optimization difficulty.

Abstract

from arXiv · show

In the past decade, sparse and low-rank recovery have drawn much attention in many areas such as signal/image processing, statistics, bioinformatics and machine learning. To achieve sparsity and/or low-rankness inducing, the $\ell_1$ norm and nuclear norm are of the most popular regularization penalties due to their convexity. While the $\ell_1$ and nuclear norm are convenient as the related convex optimization problems are usually tractable, it has been shown in many applications that a nonconvex penalty can yield significantly better performance. In recent, nonconvex regularization based sparse and low-rank recovery is of considerable interest and it in fact is a main driver of the recent progress in nonconvex and nonsmooth optimization. This paper gives an overview of this topic in various fields in signal processing, statistics and machine learning, including compressive sensing (CS), sparse regression and variable selection, sparse signals separation, sparse principal component analysis (PCA), large covariance and inverse covariance matrices estimation, matrix completion, and robust PCA. We present recent developments of nonconvex regularization based sparse and low-rank recovery in these fields, addressing the issues of penalty selection, applications and the convergence of nonconvex algorithms. Code is available at https://github.com/FWen/ncreg.git.

I. INTRODUCTION

The paper surveys nonconvex regularization for sparse and low-rank recovery across signal processing, statistics, and machine learning. It discusses penalty selection, applications, algorithmic convergence, and when convex models may remain preferable.

  • Motivation: ℓ1 and nuclear-norm penalties are tractable because of convexity, but can produce biased estimates and require more observations than nonconvex alternatives.The paper identifies ℓ0, ℓq, SCAD, and MCP as penalties that can ameliorate this bias.
  • Scope: The survey covers eight application areas, including compressive sensing, sparse regression, sparse PCA, covariance estimation, matrix completion, and robust PCA.It focuses on recent developments in nonconvex regularization-based sparse and low-rank recovery.
  • Practical guidance: Convex models may be preferable when signals are not strictly sparse, matrices are not strictly low-rank, or the signal-to-noise ratio is low.In these settings, nonconvex gains may not justify slower convergence and greater optimization difficulty.
  • Algorithms: The survey addresses penalty selection and convergence, including the absence of global convergence guarantees for many nonconvex algorithms.It contrasts these issues with convex methods that generally have stronger stability and convergence properties.
  • Methods: Proximity operators underpin efficient first-order algorithms for the nonconvex and nonsmooth problems reviewed in the paper.The survey reviews hard thresholding, ℓq shrinkage, SCAD, MCP, and firm thresholding operators.

B. Vector Proximity Operator (for Multitask Joint Sparse Recovery)

This section extends scalar nonconvex proximity operators to joint sparse recovery and generalized low-rank matrix penalties. It also connects matrix shrinkage to singular-value thresholding through the SVD.

  • Vector proximity operator: The vector proximity operator is computed element-wise because the generalized penalty is separable.This supports joint recovery of multichannel signals under a shared sparsity pattern.
  • Low-rank formulation: The generalized matrix penalty promotes low rank by applying a sparsity-inducing penalty to the matrix singular values.With ℓ0 and ℓ1 penalties, it becomes the rank and nuclear norm, respectively.
  • Matrix shrinkage: The generalized singular-value shrinkage operator applies the scalar proximity operator to the singular values and reconstructs the matrix using its SVD factors.The operator is expressed as U · diag{proxPλ(σ1, …, σr)} · V^T.

III. SPARSE VECTOR RECOVERY

This section reviews nonconvex regularization for sparse vector recovery across compressive sensing, sparse signal separation, and sparse PCA, emphasizing improved recovery, scalable algorithms, and convergence conditions.

  • Compressive Sensing: Compressive sensing reconstructs sparse signals from underdetermined measurements, where stable embedding conditions can bound recovery error by measurement noise.The sensing matrix has fewer rows than columns, making recovery generally ill-posed without sparsity and suitable matrix conditions.
  • Compressive Sensing: ℓ1 regularization can recover sparse signals reliably under RIP, null-space, or incoherence conditions but may introduce bias and require more observations.The relaxation can also produce solutions that are not sparse enough for exact recovery.
  • Compressive Sensing: PGD and ADMM provide globally convergent or stationary-point-convergent approaches for nonconvex sparse recovery, with per-iteration matrix-vector cost O(mn).PGD converges to a stationary point when L_f > λmax(A^T A), while proximal ADMM globally converges to a stationary point under suitable parameter conditions.
  • Compressive Sensing: In image reconstruction, ℓq-thresholding achieves over 60 dB PSNR for a strictly sparse synthetic image but under 30 dB for a compressible MRI image.The best q values are 0.1 for the strictly sparse image and 0.7 for the compressible image; hard- and ℓq-thresholding improve over soft-thresholding mainly for strict sparsity.

B. Sparse Regression and Variable Selection

This section surveys nonconvex penalties and optimization methods for sparse regression and variable selection in high-dimensional settings, including their statistical and computational trade-offs.

  • Sparse Regression and Variable Selection: Sparse regression simultaneously selects variables and estimates coefficients when the number of variables is comparable to or larger than the sample size.Traditional procedures such as AIC and BIC can become infeasible in this high-dimensional setting.
  • Sparse Regression and Variable Selection: LASSO, SCAD, and MCP are penalized regression approaches used to identify significant variables across linear, generalized linear, robust, Cox, and partially linear models.SCAD and MCP are nonconcave penalties proposed in the spirit of LASSO.
  • Sparse Regression and Variable Selection: Nonconvex penalized regression can be solved using local quadratic or local linear approximation, with one-step LLA methods described as more favorable than backward-stepwise LQA.The section also reviews direct coordinate-descent and cyclic-descent methods with convergence guarantees under stated conditions.
  • Sparse Regression and Variable Selection: Some nonconvex formulations enable exact control of the desired sparsity level.This property is reported among the reviewed approaches to sparse regression and variable selection.
  • Sparse Regression and Variable Selection: Nonconvex penalty performance depends heavily on initialization in experiments varying SNR and active-coefficient proportions of 2%, 5%, and 10%.The experiments compare zero initialization with initialization from the convex ℓ1 solution using PGD.

C. Sparse Signals Separation and Image Inpainting

The paper formulates sparse-signal separation and multichannel image inpainting with separate sparsity penalties, then develops proximal algorithms with stationary-point convergence guarantees. Across examples, nonconvex ℓq regularization improves restoration, while penalty parameters should reflect whether components are strictly or approximately sparse.

  • Sparse signal separation: Sparse separation demixes two sparse or approximately sparse components from mixed linear measurements, covering source separation, super-resolution, inpainting, and robust recovery.The model uses dictionaries for distinct features and can assign different sparsity penalties to the two components.
  • Sparse signal separation: Different penalties for the two components exploit their distinct sparsity properties and can outperform using the same penalty.The parameter μ accounts for statistical differences between components in the separation objective.
  • Algorithms: Proximal block-coordinate and ADMM-style updates converge to stationary points of the approximated nonconvex problem under KL and proximal-parameter conditions.The stated conditions include sufficiently large proximal parameters relative to the largest eigenvalues of A1^T A1 and A2^T A2.
  • Image inpainting: For multichannel recovery, joint sparsity models exploit correlations across RGB channels through matrix-valued component coefficients.The proximal BCD updates operate on the two multichannel components and have analogous stationary-point guarantees.
  • Image inpainting: ℓq regularization improves color-image inpainting by more than 9 dB for overwritten text and more than 5 dB for salt-and-pepper noise.The experiment represents image content with DCT coefficients and corruption with a separate sparse component.
  • Penalty selection: Small q values favor strictly sparse signals, whereas larger q values favor non-strictly sparse signals in the three evaluation cases.For example, the DCT image coefficients use relatively large q1 while strictly sparse corruption uses relatively small q2.

D. Sparse PCA

Sparse PCA seeks dimensionality reduction with interpretable loading vectors by imposing sparsity on principal components. The paper reviews constrained, penalized, greedy, relaxation, and nonconvex-penalty approaches to this problem.

  • Motivation: Sparse PCA adds sparsity to principal-component loadings so dimensionality reduction can use fewer explicitly selected variables.The paper highlights interpretability benefits in gene analysis and fewer assets, hence lower trading costs, in financial analysis.
  • Formulations: Sparse PCA can be formulated as finding an m-dimensional subspace under a sparsity constraint or through a sparsity-penalized objective.The penalty formulation uses a regularization parameter λ > 0.
  • Algorithms: A widely used greedy strategy approximately solves the multi-component problem by sequentially solving single-principal-component problems.The single-component formulation imposes both a norm constraint and a sparsity constraint.
  • Methods: Reviewed approaches include ℓ1, elastic-net, ℓ0, SCAD, robust ℓ1-loss with ℓq penalties, ADMM, and Schatten-q methods.These methods address constrained, penalized, distributed, robust, and structured sparse PCA variants.

IV. SPARSE MATRIX RECOVERY

The paper surveys nonconvex regularization for sparse matrix recovery, focusing here on large covariance and inverse covariance estimation as fundamental high-dimensional multivariate-analysis problems.

  • Scope: Large covariance and inverse covariance estimation are fundamental problems in modern multivariate analysis.The section motivates these problems by the growing availability of massive high-dimensional data.
  • Motivation: High-dimensional statistical analysis increasingly requires effective methods as information technology makes massive datasets widely available.The section frames sparse matrix recovery as a response to this modern data setting.

A. Large Sparse Covariance Matrix Estimation

The paper estimates sparse covariance matrices by thresholding sample correlations with generalized penalties, optionally enforcing positive definiteness. The resulting estimators have asymptotic optimality properties, while simulations report gains for several nonconvex penalties over ℓ1.

  • Estimation procedure: Covariance estimation is performed through the correlation matrix, then transformed back using sample variances.The correlation matrix is preferred because it has the same sparsity structure while standardizing marginal scales.
  • Thresholding estimator: Generalized thresholding solves a penalized problem on the sample correlation matrix, leaving diagonal elements unpenalized.The resulting estimator is a thresholded version of the sample correlation matrix and can be computed efficiently.
  • Positive definiteness: Finite-sample thresholding may fail to be positive-definite, despite converging to a positive-definite limit asymptotically.Adding a minimum-eigenvalue constraint simultaneously targets sparsity and positive definiteness.
  • Theory: The constrained estimator is asymptotically rate-optimal under the flexible elliptical model and achieves the minimax lower bound under the Gaussian model.The constrained and unconstrained estimators agree with overwhelming probability asymptotically over the stated covariance class.
  • Empirical evaluation: Across two simulated sparse covariance models, SCAD, hard, and ℓq penalties provide considerable performance gains over ℓ1 under spectral-norm relative error.The experiment averages results over 100 independent runs for block and banded covariance matrices of size d = 400.

B. Large Sparse Inverse Covariance Matrix Estimation

Large inverse covariance estimation models conditional correlations and seeks interpretable sparse graphs, while nonconvex penalties address bias and support favorable estimation rates. The section reviews penalized likelihood formulations, algorithms, and convergence results for this setting.

  • Problem setting: Inverse covariance matrices capture conditional correlations and support sparse graphical models for interpretable, non-overfit analysis.They also arise in high-dimensional discriminant analysis, portfolio allocation, and related applications.
  • Estimation formulation: Penalized maximum likelihood estimates the inverse covariance matrix using the sample covariance and a sparsity penalty, with positive-definiteness ensured by the logarithmic barrier.The loss is L(Θ) = tr(SΘ)−log |Θ|.
  • Algorithms and convergence: With nonconvex penalties, standard ADMM convergence is not guaranteed because the loss gradient is not Lipschitz continuous.LQA and LLA instead convert folded-concave penalization into sequences of reweighted ℓ1 problems.
  • Theory: Under Frobenius norm, penalized-likelihood estimation with a general nonconvex penalty has an established convergence rate of order s · log d/n.Here s is the number of nonzero elements, d is matrix size, and n is sample size.
  • Theory: Unlike ℓ1 penalization, unbiased nonconvex penalties such as SCAD or hard thresholding need not restrict the number of nonzero off-diagonal entries to O(d) for optimal convergence and sparsistency.The ℓ1 penalty achieves both properties only under that restriction.

V. LOW-RANK MATRIX RECOVERY

Low-rank recovery is reviewed through matrix completion, where nonconvex penalties replace nuclear-norm relaxation and are paired with proximal, factorization, and thresholding methods. The section covers recovery guarantees, convergence conditions, scalability, and image-recovery behavior across rank regimes.

  • Matrix completion: Matrix completion recovers a low-rank matrix from partially observed entries, with applications including recommender systems, computer vision, and system identification.The observed index set is modeled as a random subset of matrix entries.
  • Recovery models: Under certain conditions, nuclear-norm minimization can exactly recover a rank-r matrix from a small number of observed entries.Nonconvex penalties such as the Schatten-q norm are reviewed as alternatives to this convex relaxation.
  • Nonconvex regularization: For compressed low-rank recovery, Schatten-q regularization requires weaker sufficient conditions than nuclear-norm regularization.The section also reports proximal-descent and iteratively reweighted algorithms for nonconvex formulations.
  • Algorithms and convergence: If the generalized penalty is a closed, proper, lower-semicontinuous KL function and L_F > 1, iterative singular-value thresholding converges to a stationary point.The method is framed as both a proximal iteration and a majorization-minimization algorithm.
  • Scalable methods: Matrix factorization enables scalable low-rank recovery by updating two smaller factor matrices, even for very large problems.Scalable equivalent formulations of the Schatten-q quasi-norm support this approach.
  • Image recovery: In 512 × 512 image recovery, the best ℓq-thresholding values are q = 0.8 for non-strictly low-rank images and q = 0.2 for strictly low-rank images.The ℓ0 and ℓq penalties significantly improve over ℓ1 only in the strictly low-rank case.

B. Robust PCA

Robust PCA decomposes observations into low-rank structure and sparse corruption, extending principal-component analysis to outliers and corrupted data. The section contrasts convex formulations with nonconvex penalties and develops proximal block-coordinate methods with stationary-point convergence.

  • Problem formulation: Robust PCA seeks low-rank structure in the presence of sparse corruption, whose entries may have arbitrarily large magnitude and unknown support.Applications include video surveillance, face recognition, latent semantic indexing, ranking, and collaborative filtering.
  • Convex formulations: Using nuclear and ℓ1 penalties yields principal component pursuit, which can exactly recover the low-rank and sparse components under rather weak conditions.The model can be extended to handle both small entry-wise noise and gross sparse errors.
  • Nonconvex methods: Nonconvex penalties have been introduced to improve performance over convex nuclear and ℓ1 penalties, including q-shrinkage, alternating projection, and capped-norm methods.The reviewed approaches apply nonconvex regularization to one or both components.
  • Convergence: Except for convex methods, the reviewed nonconvex robust-PCA algorithms generally lack global convergence guarantees.A proximalized block coordinate descent method is developed for generalized nonconvex penalties G1 and G2.
  • Convergence: When G1 and G2 are closed, proper, lower-semicontinuous KL functions, proximal block coordinate descent converges to a stationary point.The method couples Gauss-Seidel updates with proximal regularization, and each subproblem can be solved using the proximity operator.

VI. OTHER APPLICATIONS INVOLVING NONCONVEX SPARSE AND LOW-RANK REGULARIZATION

The survey extends nonconvex sparse and low-rank regularization to applications including subspace learning, dictionary learning, robust fitting, deconvolution, filtering, and simultaneous sparse-low-rank recovery. It emphasizes application-dependent penalty selection alongside efficiency and unresolved convergence-rate questions.

  • Subspace Learning and Tracking: Nonconvex low-rank regularization supports subspace learning and tracking for pattern recognition, object tracking, activity recognition, video surveillance, and image classification.The Schatten-q norm has been used for these applications.
  • Dictionary Learning for Sparse Coding: Dictionary learning uses sparse coding to represent data with a few learned atoms, and ℓ0 penalties have been widely applied.The application spans signal and image processing, computer vision, and machine learning.
  • Nonconvex Regularizers with Redistributing Nonconvexity: Nonconvexity redistribution convexifies the regularization term while preserving a Lipschitz-smooth augmented loss term.This is proposed to facilitate efficient solution of nonconvex regularized problems.
  • Other applications: Nonconvex regularization has been applied to maximum-consensus robust fitting, image deconvolution and restoration, sparse system identification, and simultaneously sparse-low-rank recovery.Reported examples include ℓq image restoration, ℓ0-plus-total-variation restoration, and ℓ0-constrained LMS algorithms.
  • Penalty selection: Penalty selection should depend on intrinsic sparsity or low-rankness and noise: smaller q suits stricter structure and lower noise, whereas larger q suits weaker structure or higher noise.The survey describes this as an application-dependent choice.
  • Algorithms and open problems: First-order methods are usually most efficient, but general theoretical convergence rates remain open beyond special penalties with discontinuous thresholding functions.Sparse problems are dominated by matrix-vector multiplication, whereas low-rank problems are dominated by SVD computation per iteration.

APPENDIX A PROOF OF THEOREM 1

The proof reduces the vector proximal problem geometrically and the matrix problem spectrally. Vector minimizers align with the input, while matrix optimization separates across singular values and uses singular vectors of the input matrix.

  • Vector proximal mapping: Every vector minimizer has the form x*=αt for some α≥0.For points at equal distance from t, monotonicity of Pλ selects the point on the ray generated by t.
  • Vector proximal mapping: The vector solution uses proxPλ(∥t∥2)/∥t∥2 as its scaling factor when ∥t∥2≠0, and uses 0 when ∥t∥2=0.This scaling produces the stated vector proximal solution.
  • Special cases: For scalar inputs, the vector formula reduces to the scalar proximity operator, including the ℓ1 penalty case.The proof also identifies the ℓ0 penalty as a separate special case.
  • Matrix proximal mapping: After an SVD of X, the matrix objective is reformulated over singular vectors and nonnegative singular values with orthogonality constraints.The objective separates into summands depending on corresponding left singular vectors, right singular vectors, and singular values.
  • Matrix proximal mapping: For fixed singular values, each inner maximization selects left and right singular vectors of M associated with the corresponding singular value σi(M).This converts the matrix problem into independent scalar proximal problems for the singular values.
  • Matrix proximal mapping: The resulting singular-value optimization is itself a proximity-operator problem, yielding d∗i=proxPλ(σi(M)).Applying the scalar proximal solution to each singular value completes the matrix derivation.
Loading 1808.05403v3…