CLRMA: Compact Low Rank Matrix Approximation for Data Compression

Junhui Hou, Lap-Pui Chau, Nadia Magnenat-Thalmann, Ying HearXiv 2015 · arXiv

Introduction

Low-Rank Matrix Approximation (LRMA), often implemented via Principal Component Analysis (PCA), is a cornerstone of data compression. It decomposes a data matrix $X$ into a basis matrix $B$ and a coefficient matrix $C$. While effective at capturing inter-coherence (similarities between samples), traditional LRMA ignores intra-coherence—the spatial or structural patterns within individual samples. This results in basis vectors that contain significant redundancy, limiting compression efficiency.

Methodology: The SLRMA Framework

To overcome these limitations, the authors introduce Sparse Low-Rank Matrix Approximation (SLRMA). Unlike traditional methods that apply compression as a post-processing step, SLRMA incorporates sparsity constraints directly into the factorization process.

The SLRMA framework integrates an orthogonal transform $\Phi$ to produce a sparse basis matrix $B$.

As illustrated in the figure above, the framework introduces a prescribed orthogonal transform $\Phi$ (such as DCT or Wavelet). The objective is to find a basis $B$ that is sparse in the transform domain while minimizing reconstruction error. This joint optimization is solved using the Inexact Augmented Lagrangian Multiplier (IALM) method, ensuring the basis is inherently optimized for entropy coding.

Key Insights: Sparsity and Performance

The primary innovation of SLRMA is its ability to generate highly sparse basis vectors without sacrificing reconstruction quality. By enforcing sparsity during the factorization, the algorithm finds a basis that is inherently easier to compress.

Comparison of column vectors in standard LRMA versus SLRMA. The SLRMA vectors exhibit significantly higher sparsity.

Visual analysis of the basis vectors reveals that SLRMA successfully isolates essential features, leaving the majority of the matrix entries near zero (black). This "free" sparsity allows for much higher compression ratios. In practice, SLRMA can maintain reconstruction accuracy even when the basis vectors are 80% sparse, preserving high-frequency information that standard methods often blur.

Experimental Results

The SLRMA framework was evaluated on 2D image sets (AR and FERET datasets) and 3D dynamic meshes (sequences like "Wheel" and "Dance").

  • Image Compression: SLRMA consistently outperformed the LRMA-JP2K baseline, providing up to a 3 dB gain in Peak Signal-to-Noise Ratio (PSNR) at equivalent bit rates.
  • 3D Mesh Compression: For complex non-rigid motions, the method achieved a reduction in KG error (a standard distortion metric) of up to 53% compared to previous state-of-the-art schemes.

Conclusion

SLRMA represents a significant advancement in low-rank approximation by simultaneously exploiting inter- and intra-coherence. By embedding sparsity into the core optimization, it produces a compact representation that is highly efficient for data storage and transmission. Future work includes automating parameter selection and extending the framework to tasks like denoising and inpainting.

Summary updated

Abstract

Low-rank matrix approximation (LRMA) is a powerful technique for signal processing and pattern analysis. However, its potential for data compression has not yet been fully investigated in the literature. In this paper, we propose sparse low-rank matrix approximation (SLRMA), an effective computational tool for data compression. SLRMA extends the conventional LRMA by exploring both the intra- and inter-coherence of data samples simultaneously. With the aid of prescribed orthogonal transforms (e.g., discrete cosine/wavelet transform and graph transform), SLRMA decomposes a matrix into a product of two smaller matrices, where one matrix is made of extremely sparse and orthogonal column vectors, and the other consists of the transform coefficients. Technically, we formulate SLRMA as a constrained optimization problem, i.e., minimizing the approximation error in the least-squares sense regularized by $\ell_0$-norm and orthogonality, and solve it using the inexact augmented Lagrangian multiplier method. Through extensive tests on real-world data, such as 2D image sets and 3D dynamic meshes, we observe that (i) SLRMA empirically converges well; (ii) SLRMA can produce approximation error comparable to LRMA but in a much sparse form; (iii) SLRMA-based compression schemes significantly outperform the state-of-the-art in terms of rate-distortion performance.
BibTeX
@misc{hou2015clrma,
  author = {Junhui Hou and Lap-Pui Chau and Nadia Magnenat-Thalmann and Ying He},
  title = {{CLRMA: Compact Low Rank Matrix Approximation for Data Compression}},
  year = {2015},
  eprint = {1507.01673},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1507.01673},
}
Figure