Matching Pursuit LASSO Part II: Applications and Sparse Recovery Over Batch Signals

Mingkui Tan, Ivor W. Tsang, Li WangIEEE TSP 2015 · OpenReview

TL;DR

This paper introduces an improved sparse recovery algorithm (SMPL) that significantly speeds up existing methods by incorporating a subspace search. It then tackles the challenge of "batch sparse recovery" (processing many signals simultaneously) by developing a batch-mode MPL (BMPL), achieving up to 400x speedup over state-of-the-art methods on compressive sensing and face recognition tasks.

What Problem Does This Paper Address?

Sparse Recovery (SR) is a fundamental problem in signal processing and machine learning, aiming to reconstruct a signal that is known to be "sparse" (meaning most of its components are zero) from a limited number of measurements. The standard approach involves solving an $l_1$-norm minimization problem, which is computationally expensive, especially for large-scale problems with high-dimensional dictionaries (the measurement matrix). This paper addresses two key limitations:

  1. Efficiency of existing SR methods: While algorithms like LASSO and its variants exist, they struggle with computational complexity when dealing with very large dictionaries.
  2. Batch Sparse Recovery: A critical real-world scenario is recovering many sparse signals simultaneously (e.g., processing multiple images for face recognition). Most existing $l_1$-norm methods are not designed for this "batch" setting, leading to prohibitive computational costs.

Methods

The paper builds upon their previous work (Part I) on Matching Pursuit LASSO (MPL).

  • Subspace Exploratory Matching (SMPL): To improve MPL's performance, they introduce a "subspace exploratory matching" technique. Instead of greedily selecting a fixed number of atoms (dictionary components) per iteration, SMPL first considers a larger set of potential atoms and then selects the most beneficial ones for improving the objective function. This aims to avoid suboptimal choices and enhance convergence.
  • Batch-Mode Matching Pursuit LASSO (BMPL): This is the core contribution for handling multiple signals. BMPL reformulates the batch SR problem to efficiently compute necessary matrix products. By pre-computing certain matrices (like $A^T A$), BMPL significantly reduces the computational burden of processing many signals concurrently. This batch approach is absent in most prior $l_1$-norm methods.

Datasets

The paper evaluates their methods on:

  • Synthetic data: Gaussian random matrices and synthetic sparse signals (Bernoulli and Gaussian) are used for compressive sensing experiments.
  • Real-world datasets:
    • Extended YaleB database: Contains frontal face images used for face recognition.
  • AR database: Another face database used for face recognition experiments.

Key Insights and Ideas

  • Subspace search improves convergence: The subspace exploratory matching in SMPL leads to faster convergence and better recovery performance compared to the original MPL, especially when dealing with noisy data.
  • Batch processing is crucial for efficiency: The development of BMPL is a significant step towards making sparse recovery practical for applications involving many signals simultaneously, such as large-scale face recognition.
  • Pre-computation is key for batch efficiency: By strategically pre-computing matrices like $A^T A$, BMPL avoids redundant calculations when processing multiple signals, leading to substantial speedups.
  • Sparsity aids face recognition: The experiments suggest that sparse representations, as obtained by BMPL, PGH, and BOMP, contribute to more robust and accurate face recognition compared to non-sparse methods like L2 and L2-L2, especially under challenging conditions (e.g., varying lighting, down-sampled images).

Key Results

  • SMPL Speedup: SMPL is shown to be significantly faster than existing $l_1$-norm methods, with recovery times for large dictionaries being less than 50 seconds.
  • BMPL Speedup: BMPL achieves dramatic speedups for batch sparse recovery, being up to 400 times faster than existing $l_1$-norm methods and 7-16 times faster than batch-mode OMP (BOMP) on synthetic compressive sensing tasks.
  • Face Recognition Performance: On the Extended YaleB and AR databases, BMPL demonstrated comparable or better prediction accuracy than L2 and L2-L2 methods, often with significantly better stability. For instance, BMPL was up to 366 times faster than PGH on the AR database.
  • Efficiency on Big Dictionaries: SMPL scales well to very large dictionaries, processing signals from dictionaries with millions of atoms in under 50 seconds.

Limitations and Future Work

  • Dictionary Size Limitation for BMPL: The paper notes that BMPL's batch scheme is not applicable to dictionaries with extremely large numbers of atoms due to the $O(m^2)$ space complexity for storing the pre-computed $A^T A$ matrix. However, they state it's still feasible for dictionaries with millions of atoms on machines with sufficient memory.
  • Generalization of Subspace Search: While the subspace search in SMPL improves performance, the paper doesn't extensively explore the optimal parameters for this search across all scenarios.
  • Future Work: The paper implicitly suggests that the efficiency gains of BMPL open doors for its application in various real-world scenarios beyond face recognition, such as image processing, computer vision, and data mining, where batch processing of sparse signals is common.

Summary updated

Abstract

In Part I, a Matching Pursuit LASSO (MPL) algorithm has been presented for solving large-scale sparse recovery (SR) problems. In this paper, we present a subspace search to further improve the performance of MPL, and then continue to address another major challenge of SR-batch SR with many signals, a consideration which is absent from most of previous l1-norm methods. A batch-mode MPL is developed to vastly speed up sparse recovery of many signals simultaneously. Comprehensive numerical experiments on compressive sensing and face recognition tasks demonstrate the superior performance of MPL and BMPL over other methods considered in this paper, in terms of sparse recovery ability and efficiency. In particular, BMPL is up to 400 times faster than existing l1-norm methods considered to be state-of-the-art.
BibTeX
@article{tan2015matching,
  author = {Mingkui Tan and Ivor W. Tsang and Li Wang},
  title = {{Matching Pursuit LASSO Part II: Applications and Sparse Recovery Over Batch Signals}},
  journal = {IEEE Trans. Signal Process.},
  year = {2015},
  url = {https://openreview.net/forum?id=g7f66yxBmYL},
}
Figure