Sparse approximation based on a random overcomplete basis

Yoshinori Nakanishi-Ohno, Tomoyuki Obuchi, Masato Okada, Yoshiyuki Kabashima

TL;DR

This paper investigates sparse approximation using random overcomplete bases, comparing $\ell_0$ and $\ell_1$ minimization strategies. They find that the $\ell_0$ method, which aims for the absolute minimum distortion, significantly outperforms the $\ell_1$ method, even when practical algorithms like OMP and AMP are used. This work provides a theoretical framework for understanding the trade-offs in sparse approximation and suggests avenues for designing more efficient algorithms.

What Problem Does This Paper Address?

The core problem this paper tackles is sparse approximation, which is the task of representing a data vector using a small number of non-zero coefficients from a given set of basis vectors. This is crucial in many areas, from signal processing and image compression to machine learning, as it allows for efficient data representation and compression. The authors specifically focus on using an overcomplete basis (OCB), which contains more basis vectors than the dimension of the data. This offers the potential for better representations but introduces the challenge of selecting the optimal subset of basis vectors. The paper aims to understand the performance trade-offs between different methods for selecting these basis vectors, particularly the $\ell_0$ and $\ell_1$ minimization approaches, and to evaluate practical algorithms for these methods.

Methods

The paper employs a combination of theoretical and numerical methods:

  • Statistical Mechanics: For theoretical analysis, especially in the large system limit ($M \to \infty$), the authors leverage tools from statistical mechanics, including the replica method and saddle-point approximation. This allows them to derive analytical expressions for performance metrics like distortion and compression rate.
  • $\ell_0$-based Method: This method aims to find the absolute minimum distortion by selecting exactly $rM$ basis vectors. Theoretically, this involves an exhaustive search, which is computationally intractable for large systems. The paper analyzes its ideal performance using statistical mechanics.
  • $\ell_1$-based Method: This method uses $\ell_1$-norm regularization (similar to LASSO) to achieve sparsity. It's computationally more tractable than the $\ell_0$ method. The paper analyzes its performance, including a post-processing step using least squares (LS) to further reduce distortion.
  • Greedy Algorithms (OMP): Orthogonal Matching Pursuit (OMP) is investigated as a practical, computationally efficient algorithm for approximating the $\ell_0$-based method.
  • Approximate Message Passing (AMP): AMP is studied as a practical algorithm for implementing the $\ell_1$-norm regularization.
  • Numerical Simulations: The theoretical results are validated through simulations on finite-size systems, with extrapolations to the infinite-size limit.
  • Image Data Compression: The practical performance of OMP and AMP is demonstrated on image data compression tasks.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated from:

  • Data Vectors ($y$): Independently and identically distributed (i.i.d.) random variables from a normal distribution with mean 0 and variance $\sigma_y^2$.
  • Basis Matrix ($A$): Elements are i.i.d. random variables from a normal distribution $N(0, M^{-1})$.

For the image data compression application, standard image data is used, but specific datasets are not named.

Key Insights and Ideas

  • $\ell_0$ Dominance: The $\ell_0$-based method, which seeks the true minimum distortion, consistently and significantly outperforms the $\ell_1$-based method, even when the latter is enhanced with post-processing (LS). This highlights the theoretical advantage of directly minimizing the number of non-zero elements.
  • Achievable Distortion: For any fixed compression rate ($r$), arbitrarily small distortion is achievable in the large-size limit of the overcomplete basis, by increasing the degree of overcompleteness ($\alpha$). This is a powerful insight for designing systems with specific distortion targets.
  • Overcompleteness Trade-off: Increasing the degree of overcompleteness ($\alpha$) generally leads to better trade-off relations (lower distortion for a given rate), but the required size of the overcomplete basis grows polynomially for $\ell_0$ and exponentially for $\ell_1$ as distortion decreases.
  • Practical Algorithms: Orthogonal Matching Pursuit (OMP) shows much better performance than the exact $\ell_1$-based method and Approximate Message Passing (AMP), suggesting that greedy algorithms might be more suitable for sparse approximation with OCBs than convex relaxation methods.
  • LS Post-processing: The method of Least Squares (LS) after $\ell_1$-norm regularization is shown to effectively reduce distortion, even eliminating it in the ideal limit $\alpha \to 0$, which is not achieved by $\ell_1$-norm regularization alone.

Key Results

  • Trade-off Curves: Figure 5(a) clearly shows that both $\ell_0$ and $\ell_1$-based methods (with OCB) achieve better rate-distortion trade-offs than the naive (least squares) method.
  • $\ell_0$ vs. $\ell_1$ Performance: The $\ell_0$-based method consistently yields lower distortion for a given compression rate compared to the $\ell_1$-based method across various scenarios.
  • Algorithm Performance: OMP demonstrates superior performance to AMP and the exact $\ell_1$-based method in terms of the trade-off relation. For image compression, OMP achieved higher PSNR (28.2) than AMP (22.9) for similar compression rates, though at a significantly higher computational cost.
  • Computational Cost Scaling: The required size of the overcomplete basis scales polynomially with distortion for the $\ell_0$ method and exponentially for the $\ell_1$ method.

Limitations and Future Work

  • Computational Cost of $\ell_0$: The exhaustive search for the $\ell_0$-based method is computationally prohibitive for large systems. While OMP is a good practical approximation, the paper suggests there is "still room to design more effective greedy algorithms" for the $\ell_0$-based method.
  • $\ell_1$ Inferiority: The authors attribute the inferiority of the $\ell_1$-based method to the regularization term, which, while useful for rate reduction, distorts the primary goal of minimizing distortion.
  • Basis Selection: The paper uses a random overcomplete basis. The authors note that finding a "proper basis for sparse approximation in advance" is challenging, and suggest that combining their methods with "dictionary learning" could be a promising direction for future work to improve efficiency.
  • Algorithm Exploration: Further research is underway to design more effective greedy algorithms than OMP for the $\ell_0$-based method.

Summary updated

Abstract

We discuss a strategy of sparse approximation that is based on the use of an overcomplete basis, and evaluate its performance when a random matrix is used as this basis. A small combination of basis vectors is chosen from a given overcomplete basis, according to a given compression rate, such that they compactly represent the target data with as small a distortion as possible. As a selection method, we study the $\ell_0$- and $\ell_1$-based methods, which employ the exhaustive search and $\ell_1$-norm regularization techniques, respectively. The performance is assessed in terms of the trade-off relation between the representation distortion and the compression rate. First, we evaluate the performance analytically in the case that the methods are carried out ideally, using methods of statistical mechanics. Our result clarifies the fact that the $\ell_0$-based method greatly outperforms the $\ell_1$-based one. Second, we examine the practical performances of two well-known algorithms, orthogonal matching pursuit and approximate message passing, when they are used to execute the $\ell_0$- and $\ell_1$-based methods, respectively. Our examination shows that orthogonal matching pursuit achieves a much better performance than the exact execution of the $\ell_1$-based method, as well as approximate message passing. However, regarding the $\ell_0$-based method, there is still room to design more effective greedy algorithms than orthogonal matching pursuit. Finally, we evaluate the performances of the algorithms when they are applied to image data compression.
BibTeX
@article{nakanishiohno2016sparse,
  author = {Yoshinori Nakanishi-Ohno and Tomoyuki Obuchi and Masato Okada and Yoshiyuki Kabashima},
  title = {{Sparse approximation based on a random overcomplete basis}},
  journal = {Journal of Statistical Mechanics Theory and Experiment},
  year = {2016},
  doi = {10.1088/1742-5468/2016/06/063302},
}
Figure