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.

    Source: §I · p. 2, §X · p. 32

  • Method

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

    Source: A. Sparse representation in dictionary… · p. 19, §X · pp. 32–33

  • Results

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

    Source: C. Discussion · p. 32

  • Takeaways & Limitations

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

    Source: §X · p. 33

    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.

    Source: §X · p. 33

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.Source: §I · p. 1
  • Compressed sensing links sparse signals to reconstruction from measurements substantially fewer than those required by traditional sampling theories.Source: §I · p. 1
  • Sparse representation methods can be categorized by atoms, representation type, methodology, and optimization viewpoint.Source: A. Categorization of sparse… · p. 2

Greedy strategy approximation

Constrained optimization strategy

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.Source: A. Sparse representation with l0-norm… · p. 6
  • 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.Source: A. Sparse representation with l0-norm… · p. 6

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.Source: A. Sparse representation with l0-norm… · p. 6

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.Source: A. Sparse representation with l0-norm… · p. 6

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.Source: B. Sparse representation with l1-norm… · pp. 6–7

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.Source: C. Sparse representation with lp-norm… · p. 7

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.Source: D. Sparse representation with… · p. 7
  • 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 µ.Source: D. Sparse representation with… · p. 7

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.Source: §IV · p. 7, C. Series of matching pursuit algorithms · p. 8
  • 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.Source: A. Matching pursuit algorithm · pp. 7–8
  • 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.Source: B. Orthogonal matching pursuit algorithm · p. 8

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.Source: §V · pp. 8–9, A. Gradient Projection Sparse… · p. 9

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.Source: B. Interior-point method based sparse… · pp. 9–10
  • 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.Source: B. Interior-point method based sparse… · pp. 9–10

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.Source: B. Interior-point method based sparse… · p. 10
  • 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.Source: B. Interior-point method based sparse… · p. 10

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 α.Source: B. Interior-point method based sparse… · p. 10

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.Source: B. Interior-point method based sparse… · p. 10

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.Source: C. Alternating direction method (ADM)… · pp. 10–11
  • 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.Source: C. Alternating direction method (ADM)… · p. 11

Subproblem solutions

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.Source: C. Alternating direction method (ADM)… · p. 11

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.Source: §VI · p. 11
  • The shrinkage operator solves the scalar l1-regularized subproblem by retaining values outside the threshold and setting intermediate values to zero.Source: A. Soft thresholding or shrinkage… · p. 12
  • The general l1-regularized sparse-representation objective combines a quadratic reconstruction term with an l1 penalty.Source: B. Iterative shrinkage thresholding… · p. 12
  • 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.Source: B. Iterative shrinkage thresholding… · p. 12

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)

l1/2-norm regularization based sparse representation

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.

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.

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.Source: §VII · p. 16
  • The LASSO homotopy algorithm decreases λ from a large value toward zero, with appropriate parameter values linking its formulation to the LASSO problem.Source: A. LASSO homotopy · p. 16
  • KKT conditions are maintained on the support Λ and its complement as λ decreases, using residual correlations p, directional changes q, and update direction δ.Source: A. LASSO homotopy · pp. 16–17
  • At each critical point, the algorithm either adds an inactive element to the support or removes an active element whose coefficient shrinks to zero.Source: A. LASSO homotopy · p. 17
  • Each iteration computes an update direction and step size, updates α and the support/sign sequence, and stops when ∥p∥∞= 0.Source: A. LASSO homotopy · p. 17

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.Source: B. BPDN homotopy · p. 17
  • At each critical point, one inactive element enters the active set or one nonzero active coefficient reaches zero and is removed.Source: B. BPDN homotopy · p. 17
  • The BPDN homotopy algorithm is described as computationally efficient and terminates when λ falls below its desired value.Source: B. BPDN homotopy · p. 18

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.

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.

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.Source: B. Sparse representation in image… · pp. 25–26

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.Source: B. Sparse representation in image… · p. 25
  • 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.Source: B. Sparse representation in image… · p. 25
  • 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.Source: B. Sparse representation in image… · p. 25
  • 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.Source: B. Sparse representation in image… · p. 25

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.Source: B. Sparse representation in image… · pp. 25–26

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.Source: C. Sparse representation in image… · pp. 28–29

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.Source: C. Sparse representation in image… · p. 28
  • 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.Source: C. Sparse representation in image… · p. 28
  • 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.Source: C. Sparse representation in image… · pp. 28–29

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.Source: C. Sparse representation in image… · p. 29

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.Source: §IX · p. 29

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.Source: Figure 5 · p. 30

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.Source: §IX · p. 30
  • 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.Source: §IX · p. 30
  • COIL20 contains 1,440 grayscale images of 20 objects captured across 360° at five-degree pose intervals.Each object has 72 images.Source: §IX · pp. 30–31
  • 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.Source: §IX · p. 31

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.Source: A. Parameter selection · p. 31

Experimental results

  • The l1ls algorithm achieves the highest ORL classification result of 95.90% when each class has five training samples.Source: B. Experimental results · p. 31
  • TPTSR has classification accuracies similar to, and sometimes better than, other sparse representation classification algorithms while requiring substantially less computation.Source: B. Experimental results · p. 31

Computational efficiency

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.Source: C. Discussion · pp. 31–32, §X · p. 33

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.Source: C. Discussion · p. 32

Related papers

Loading 1602.07017v1…