PaperlayerView exact revision on arXiv

Source-linked AI summary

A survey of sparse representation: algorithms and applications

Zheng Zhang, Yong Xu, Jian Yang, Xuelong Li, David Zhang

arXiv:1602.07017v1cs.CVcs.LG

TL;DR

Sparse representation requires a coherent account of diverse methods, algorithms, and applications across theoretical and practical settings. This paper surveys the field, categorizes algorithms into four optimization-oriented groups, and compares representative methods experimentally. It concludes that no single algorithm is best across all datasets and that efficiency and robustness remain important challenges for real-world use.

  • Problem

    Sparse representation spans many methods and applications, motivating an updated survey that organizes algorithms and clarifies their relationships and uses.

  • Method

    The paper synthesizes sparse representation theory, categorizes algorithms into greedy, constrained optimization, proximity-based, and homotopy groups, and reviews dictionary learning and applications.

  • Results

    Experiments compare sparse representation algorithms across classification datasets, finding no absolute winner for both classification accuracy and computational efficiency.

  • Takeaways & Limitations

    Sparse representation remains broadly used, while future methods need greater efficiency and robustness for real-world and large-scale applications.

  • Takeaways & Limitations

    The effectiveness and efficiency of sparse representation methods do not perfectly meet real-world needs, especially for large-scale problems and robustness to image corruptions and occlusions.

Abstract

from arXiv · show

Sparse representation has attracted much attention from researchers in fields of signal processing, image processing, computer vision and pattern recognition. Sparse representation also has a good reputation in both theoretical research and practical applications. Many different algorithms have been proposed for sparse representation. The main purpose of this article is to provide a comprehensive study and an updated review on sparse representation and to supply a guidance for researchers. The taxonomy of sparse representation methods can be studied from various viewpoints. For example, in terms of different norm minimizations used in sparsity constraints, the methods can be roughly categorized into five groups: sparse representation with $l_0$-norm minimization, sparse representation with $l_p$-norm (0$<$p$<$1) minimization, sparse representation with $l_1$-norm minimization and sparse representation with $l_{2,1}$-norm minimization. In this paper, a comprehensive overview of sparse representation is provided. The available sparse representation algorithms can also be empirically categorized into four groups: greedy strategy approximation, constrained optimization, proximity algorithm-based optimization, and homotopy algorithm-based sparse representation. The rationales of different algorithms in each category are analyzed and a wide range of sparse representation applications are summarized, which could sufficiently reveal the potential nature of the sparse representation theory. Specifically, an experimentally comparative study of these sparse representation algorithms was presented. The Matlab code used in this paper can be available at: http://www.yongxu.org/lunwen.html.

I. INTRODUCTION

Sparse representation is presented as a powerful framework related to compressed sensing and applied across signal processing, image processing, computer vision, and pattern recognition. The survey organizes existing methods by optimization strategy, explains representative algorithms, and reviews applications and experiments.

  • Sparse representation supports applications including image denoising, deblurring, inpainting, restoration, super-resolution, tracking, classification, and segmentation.
  • Compressed sensing links sparse signals to reconstruction from measurements substantially fewer than those required by traditional sampling theories.
  • Sparse representation methods can be categorized by atoms, representation type, methodology, and optimization viewpoint.
  • Greedy strategy approximation: Greedy approximation addresses l0-norm minimization by iteratively selecting locally optimal samples to construct a k-sparse approximation.
  • Constrained optimization strategy: Constrained optimization reformulates convex but nonsmooth l1-norm minimization into a differentiable constrained problem.
  • The survey covers proximity and homotopy strategies, summarizes representative algorithms and applications, and provides extensive experimental evaluations.

III. SPARSE REPRESENTATION PROBLEM WITH DIFFERENT

Sparse representation models represent a probe sample as a linear combination of atoms while imposing sparsity constraints on the coefficient vector. The section introduces l0-, lp-, and l1-based formulations, including noisy and constrained variants.

  • General formulation: Sparse representation uses an over-completed dictionary X to represent a probe sample y through coefficients α.Each column of X is a known sample or atom, and α contains the corresponding representation coefficients.
  • General formulation: Without prior knowledge or constraints, the underdetermined representation system is ill-posed, motivating sparsity constraints on α.Sparsity means that many coefficients are zero or close to zero while only a few are substantially nonzero.
  • l0-norm minimization: The l0-norm formulation seeks the sparsest representation by minimizing the number of nonzero coefficients, with the k-sparse variant restricting the representation to k atoms.The l0-norm is defined as the number of nonzero elements in the coefficient vector.
  • Noisy formulation: Because real data contain noise, the model introduces representation noise s bounded by ∥s∥2 ≤ ε and solves approximate sparse-representation problems.The noisy formulation revises the original linear model before optimization.
  • l1-norm minimization: The l1-norm is widely used because l0-norm minimization is NP-hard and difficult to solve directly.The section presents l1-based sparse representation as an extensively developed alternative for machine learning, pattern recognition, and statistics.
  • lp-norm minimization: For 0<p<1, lp-norm minimization is studied as a non-mainstream approach that nevertheless influences improvements in sparse representation theory.Examples include p = 0.1, 0.3, and 0.9.

D. Sparse representation with l2,1-norm minimization

This material contrasts limited sparsity under l2 minimization with robust l2,1 formulations, then surveys greedy and constrained optimization strategies for sparse representation.

  • Norm formulations: l2-norm minimization produces a ‘limitedlysparse’ solution that is discriminative and distinguishable but not rigorously sparse.The section contrasts this behavior with formulations designed to obtain stronger sparsity.
  • Norm formulations: The l2,1-norm, also called the rotation invariant l1-norm, is proposed to improve robustness to outliers.Its objective uses sample matrices Y and coefficient matrix A with a small positive parameter µ.
  • Greedy strategy approximation: Greedy sparse-representation algorithms select atoms using their relationship with the probe sample and estimate amplitudes with least squares.They provide approximate solutions for the NP-hard l0-norm problem rather than directly solving its optimization formulation.
  • Greedy strategy approximation: Matching pursuit iteratively selects the dictionary atom with the strongest similarity to the current residual and updates the representation residual.The process continues until the residual is below a prescribed tolerance.
  • Greedy strategy approximation: Orthogonal matching pursuit improves matching pursuit by orthogonalizing the projection direction at each iteration and can converge in limited iterations.Its procedure repeatedly selects a matching sample, updates the active set, computes least-squares coefficients, and updates the residual.
  • Constrained optimization: Constrained optimization methods reformulate non-differentiable l1-regularized problems as smooth constrained problems to obtain sparse solutions with efficient convergence.GPSR uses positive and negative coefficient parts, gradient descent, and backtracking line search.

B. Interior-point method based sparse representation strategy

The interior-point strategy converts the nonsmooth l1 problem into smooth optimization problems and uses Newton-based procedures to obtain sparse representations.

  • Strategy: Interior-point methods transform the original unconstrained nonsmooth l1 problem into a constrained smooth optimization problem.The strategy then converts the constrained problem into an unconstrained smooth problem using a barrier function.
  • Strategy: The barrier function forces optimization to remain within the feasible region during the unconstrained procedure.The method uses a positive parameter σ in the reformulated problem.
  • Truncated Newton procedure: The truncated Newton method solves the resulting smooth problem using a Newton system and a Hessian approximated with preconditioned conjugate gradients.A linear-search direction is then obtained from the Newton system.
  • Truncated Newton procedure: The method constructs a Lagrangian dual, a dual-feasible point, and a duality gap for the l1 optimization problem.Backtracking linear search determines the Newton step size and supports termination through the duality gap.
  • Algorithm: TNIPM iteratively computes a search direction, selects a step size, updates the iteration point, and stops when its termination tolerance is satisfied.The algorithm outputs the coefficient vector α.
  • Applications: The truncated Newton based interior-point method is described as effective for l1-norm regularization and has also been used for large-scale logistic regression.The logistic-regression application uses preconditioned conjugate gradients and warm-start techniques.

C. Alternating direction method (ADM) based sparse representation strategy

The ADM strategy separates the l1-regularized problem with an auxiliary variable, alternately updates its variables and multiplier, and uses soft thresholding within the resulting subproblems.

  • ADM formulation: ADM introduces an auxiliary variable to convert the original l1-regularized problem into a constrained optimization problem.The constrained formulation is represented through an augmented Lagrangian.
  • ADM formulation: ADM alternately minimizes the augmented Lagrangian with respect to the auxiliary variable and coefficient vector, then updates the Lagrange multiplier.The general updates are given for s, α, and λ at each iteration.
  • Subproblem solutions: The coefficient subproblem can be approximately solved with a second-order Taylor expansion of the function f(α).This approximation produces the inexact or approximate ADM variant.
  • Subproblem solutions: The auxiliary-variable subproblem has a solution given by the soft thresholding operator.The operator is defined as soft(σ, η) = sign(σ) max{|σ| −η, 0}.
  • Algorithm: The summarized ADM algorithm initializes the variables, repeatedly updates s, α, and λ, increases µ by τ, and outputs the updated coefficient vector.The procedure continues while the optimization has not converged.

VI. PROXIMITY ALGORITHM BASED OPTIMIZATION

Proximity algorithms solve constrained convex sparse-representation problems by iteratively applying proximal operators to simpler subproblems. For l1 regularization, ISTA derives a shrinkage-based update through linearization or preconditioning.

  • Proximity algorithms use proximal operators to iteratively solve nonsmooth, constrained convex optimization subproblems more efficiently than the original problem.
  • The shrinkage operator solves the scalar l1-regularized subproblem by retaining values outside the threshold and setting intermediate values to zero.
  • The general l1-regularized sparse-representation objective combines a quadratic reconstruction term with an l1 penalty.
  • ISTA linearizes the quadratic term, approximates its Hessian, and updates coefficients using αt+1 = shrink(θ(αt), λτ).The gradient and Hessian of the quadratic term are ∇f(α) = X^T(Xα − y) and Hf(α) = X^T X.

C. Fast Iterative shrinkage thresholding algorithm (FISTA)

FISTA improves ISTA’s proximal optimization by using a Lipschitz-based Hessian approximation and an extrapolated sequence of iteration points. Related proximity methods extend these ideas through adaptive continuation, spectral steps, and nonconvex thresholding.

  • Fast Iterative shrinkage thresholding algorithm (FISTA): FISTA preserves ISTA’s efficiency while improving its effectiveness and obtaining global convergence.
  • Fast Iterative shrinkage thresholding algorithm (FISTA): FISTA uses the minimum Lipschitz constant of ∇f(α) to approximate the Hessian, with L(f) = 2λmax(X^T X).
  • Fast Iterative shrinkage thresholding algorithm (FISTA): FISTA accelerates convergence by replacing the previous iteration point with a specific linear combination of the two preceding points.
  • Fast Iterative shrinkage thresholding algorithm (FISTA): SpaRSA adapts ISTA through decreasing regularization parameters and Barzilai-Borwein spectral steps that approximate the Hessian.
  • l1/2-norm regularization based sparse representation: The l1/2 regularization approach uses a half proximal algorithm and thresholding operator for a nonconvex, nonsmooth, and non-Lipschitz optimization problem.

F. Augmented Lagrange Multiplier based optimization strategy

Augmented Lagrangian methods address l1-regularized sparse representation by converting equality-constrained formulations into augmented optimization problems. PALM alternates coefficient and multiplier updates, while DALM applies the same framework to the dual problem.

  • The augmented Lagrangian method converts the equality-constrained sparse-representation problem into an unconstrained problem with a weighted constraint term.
  • The augmented Lagrangian jointly optimizes sparse coefficients and a Lagrange multiplier vector through alternating updates.
  • PALM solves the primal augmented-Lagrangian formulation, with its coefficient subproblem addressed using FISTA before updating the dual variable.
  • DALM applies the augmented Lagrangian method to the dual function of the l1-regularized sparse-representation problem.
  • Projection onto the l∞ ball acts as a proximal operator and is implemented through group-wise soft-thresholding.

G. Other proximity algorithm based optimization methods

Other proximity methods construct proximal operators and introduce algorithmic improvements aimed at increasing effectiveness and efficiency. Examples include coordinate descent and approximate message passing.

  • The theoretical basis of proximity algorithms is constructing a proximal operator and using it to solve a convex optimization problem.
  • PCDA introduces element-wise optimization into an iterative method for sparse representation.
  • AMP modifies iterative thresholding using ideas from belief propagation to match the sparsity undersampling tradeoff of the corresponding convex optimization approach.

VII. HOMOTOPY ALGORITHM BASED SPARSE

Homotopy methods solve l1-norm sparse-representation problems by tracing a parameterized solution path while maintaining optimality conditions and updating the active support at critical points.

  • Homotopy traces a continuous parameterized path of solutions as optimization parameters vary, connecting sparse-representation problems with LAR, OMP, and PFP.
  • The LASSO homotopy algorithm decreases λ from a large value toward zero, with appropriate parameter values linking its formulation to the LASSO problem.
  • KKT conditions are maintained on the support Λ and its complement as λ decreases, using residual correlations p, directional changes q, and update direction δ.
  • At each critical point, the algorithm either adds an inactive element to the support or removes an active element whose coefficient shrinks to zero.
  • Each iteration computes an update direction and step size, updates α and the support/sign sequence, and stops when ∥p∥∞= 0.

B. BPDN homotopy

BPDN homotopy methods trace sparse solutions as λ decreases, using critical-point updates that change the active set one element at a time; weighted variants extend this path-following strategy.

  • BPDN homotopy is closely related to LASSO homotopy and derives its solution from KKT optimality conditions for the sparse optimization problem.
  • At each critical point, one inactive element enters the active set or one nonzero active coefficient reaches zero and is removed.
  • The BPDN homotopy algorithm is described as computationally efficient and terminates when λ falls below its desired value.

VIII. THE APPLICATIONS OF THE SPARSE

Sparse representation applications include image processing, recognition, signal processing, and dictionary learning; dictionary methods learn atoms and sparse codes through alternating optimization and sparse coding.

  • Sparse representation has been applied to image denoising, deblurring, inpainting, super-resolution, restoration, classification, segmentation, signal processing, and object tracking.
  • Dictionaries can be constructed from transform functions or learned from data, and dictionary choice affects reconstruction quality and task performance.
  • Dictionary learning minimizes reconstruction error over a dictionary D and sparse codes xi, with P(xi) and λ controlling regularization and sparsity.
  • The review separates dictionary learning into supervised and unsupervised classes according to whether class labels are used during learning.
  • K-SVD alternates sparse coding and dictionary updates, using l0-norm sparse coding and SVD-based atom updates while preserving nonzero coefficients.
  • K-SVD updates each atom from the corresponding representation residual, retaining only relevant nonzero coefficients before SVD decomposition.

2) Supervised dictionary learning:

Supervised dictionary learning incorporates label or discriminative information into dictionary and classifier learning for image classification, using joint objectives and class-structured criteria.

  • DKSVD jointly learns a discriminative dictionary and classifier parameters, then uses OMP sparse codes with the learned classifier for classification.
  • LC-KSVD uses supervised information and is described as preventing suboptimal or local optimal dictionary-learning solutions compared with other methods.
  • LC-KSVD combines reconstruction, discriminative sparse-code, and classification errors in a joint objective for learning a dictionary and classifier parameter.
  • FDDL incorporates class labels and Fisher discrimination into dictionary learning to construct a structured discriminative dictionary for pattern classification.
  • FDDL jointly constructs a discriminative dictionary and discriminative sparse coefficients through fidelity, sparse-regularization, and discriminative-coefficient terms.

B. Sparse representation in image processing

Sparse representation supports image reconstruction tasks by combining learned dictionaries, sparse coding, and reconstruction constraints. The section surveys super-resolution and denoising pipelines that operate on image patches and enforce global consistency.

  • Applications: Sparse representation applications in image processing include super-resolution, denoising, and restoration, with later work extending the approach through jointly learned or coupled dictionaries.The survey also describes Bayesian and global-constraint formulations for image reconstruction.
  • Super-resolution: Super-resolution reconstructs a high-resolution image from a low-resolution counterpart using coupled low- and high-resolution patch dictionaries.The low-resolution dictionary is used to recover high-resolution patches through the corresponding high-resolution dictionary.
  • Super-resolution: The super-resolution problem is ill-posed because a given low-resolution image can correspond to infinitely many solutions.Sparse representation introduces a prior that image patches are approximately represented by a few training samples from the high-resolution dictionary.
  • Super-resolution: The SRSR pipeline estimates sparse coefficients for each patch, reconstructs high-resolution patches, and enforces compatibility across overlapping patches.The local model phase processes patches individually, while an enhanced global reconstruction constraint improves consistency with adjacent patches.
  • Super-resolution: A second SRSR phase projects the initially reconstructed image onto the global reconstruction-constraint space before producing the final high-resolution image.The final image is obtained after solving the global problem, with back-projection used as the solution method.
  • Image denoising: Image denoising separates sparse image components treated as useful information from residual components treated as noise before reconstructing the image.The reviewed framework partitions degraded images into overlapping patches, constructs or updates dictionaries, reconstructs patches, averages overlaps, and repeats until termination.

C. Sparse representation in image classification and visual tracking

Sparse representation is applied to image classification and visual tracking through sparse coding of test samples or target candidates. Reported classification results indicate robustness to several image degradations, while related methods extend the framework with alternative regularization and tracking strategies.

  • Applications: Sparse representation methods have been studied extensively for image classification, face recognition, visual tracking, and vehicle classification.The survey presents these applications as major computer vision and pattern recognition areas for sparse representation.
  • Image classification: Experimental results suggest that sparse representation based classification can somewhat overcome illumination changes, random pixel corruption, large block occlusion, and disguise.The statement describes robustness across these challenging image conditions without claiming complete invariance.
  • Image classification: SRC represents a test sample as a linear combination of training samples and assigns its class using the smallest class-specific reconstruction residual.The classification pipeline normalizes samples, solves an l1-norm representation problem, and selects the class with minimum residual.
  • Image classification: Face-recognition variants modify regularization, impose nonnegative constraints, use maximum correntropy, or apply iteratively reweighted robust coding.These methods target robustness, effectiveness, or efficiency in sparse representation based classification.
  • Visual tracking: Visual tracking methods combine sparse constraints with particle filters, dynamic template updating, dimension reduction, or OMP to represent targets using few templates and improve recovery efficiency.Some approaches also fuse background templates into tracking for robust object tracking.

IX. EXPERIMENTAL EVALUATION

The experimental evaluation compares representative sparse representation based classification algorithms on face and object-categorization datasets. It specifically studies how classification accuracy changes with the regularization parameter λ.

  • Compared methods: The evaluation compares OMP, l1-based methods, FISTA, DALM, homotopy, and TPTSR for object categorization.These algorithms represent greedy, optimization, proximal, and homotopy-based sparse representation approaches.
  • Parameter evaluation: Fig. 5 plots classification accuracy against the regularization parameter λ on ORL, LFW, COIL20, and Fifteen scene datasets.The figure includes two face datasets and two object datasets.
  • Datasets: The ORL database contains 400 face images from 40 subjects, with variation in lighting, facial expressions, and facial details.Images were resized to 56×46 matrices for the experiments.
  • Datasets: The LFW experiments selected 1251 images from 86 people, with each subject contributing 10–20 images resized to 32×32 pixels.LFW is designed for unconstrained identity verification and face recognition.
  • Datasets: COIL20 contains 1,440 grayscale images of 20 objects captured across 360° at five-degree pose intervals.Each object has 72 images.
  • Datasets: Fifteen scene contains 4,485 images across 15 natural indoor and outdoor scene categories.The dataset includes categories such as office, kitchen, street, highway, coast, mountain, forest, and suburb.

A. Parameter selection

The paper evaluates sparse representation algorithms across parameter settings, classification tasks, accuracy, and computational cost. Results show that parameter choice materially affects performance, while no single method is best across all datasets and criteria.

  • Parameter selection: Regularization parameter λ can significantly affect classification results, and the best value differs across datasets.TPTSR is reported as nearly insensitive to λ variation in the evaluated datasets.
  • Experimental results: The l1ls algorithm achieves the highest ORL classification result of 95.90% when each class has five training samples.
  • Experimental results: TPTSR has classification accuracies similar to, and sometimes better than, other sparse representation classification algorithms while requiring substantially less computation.
  • Computational efficiency: OMP and TPTSR have the lowest computational times because they use fast least-squares techniques instead of iterative l1-norm minimization.
  • Limitations and future directions: Sparse representation remains challenged by parameter tuning, computational complexity, insufficient robustness, and inferior results on some difficult datasets such as LFW.
  • Overall comparison: The l1ls, homotopy, and TPTSR algorithms achieve the best overall recognition performance, but no algorithm performs best on every dataset for both accuracy and efficiency.
Loading 1602.07017v1…