Better than best low-rank approximation with the singular value decomposition

David F. GleicharXiv 2024 · DOI · arXiv

Abstract

The Eckart-Young theorem establishes the Singular Value Decomposition (SVD) as the mathematically optimal low-rank approximation for any given matrix. However, this optimality is strictly tied to the specific matrix structure provided. This paper demonstrates that by reorganizing or reshaping data before applying the SVD, it is possible to achieve approximations that are significantly more accurate and parameter-efficient than the "best" standard SVD. Through techniques like image tiling and temporal reshaping, we show that the way data is organized into a matrix is a critical, yet often overlooked, factor in compression performance.

Introduction

In data science, low-rank approximations like Principal Component Analysis (PCA) and SVD are fundamental tools for data compression and pattern discovery. We often treat the initial matrix representation of our data as a fixed constraint, relying on the Eckart-Young theorem to guarantee that our SVD-based reconstruction is the best possible solution for minimizing error.

This paper challenges that assumption by highlighting that "the data" and "the matrix" are not synonymous. The choice of how to map data into a matrix structure can either hide or reveal underlying patterns. By strategically reorganizing data, we can achieve results that are "better than best"—surpassing the theoretical limits of the standard SVD applied to the original matrix layout.

Methods of Data Reorganization

The study explores three primary strategies for improving SVD performance through reorganization:

1. Matrix-of-Tiles (Kronecker Product SVD)

Instead of representing an image as a standard $m \times n$ grid of pixels, the image is decomposed into small $k \times k$ tiles. Each tile is vectorized into a single column of a new, taller matrix. This approach, mathematically equivalent to a Kronecker product SVD, allows the decomposition to identify "basis tiles" rather than global row/column patterns. This better exploits the local correlations inherent in natural images.

Figure 6: The "Matrix-of-Tiles" approach involves breaking an image into a grid of small tiles before vectorization and SVD.

2. Temporal Reshaping

For time-series data, the paper compares a standard "states-by-days" matrix against a reshaped version where time segments are stacked. This transformation effectively converts a global low-rank approximation into a piecewise-linear one, allowing the SVD to capture local trends that would otherwise be smoothed over in a global model.

3. Diagonal Reorganization

In a theoretical proof, the author demonstrates that for certain matrices (such as the inverse of a tridiagonal matrix), moving the main diagonal into its own column allows a rank-1 approximation to capture nearly all the energy. In contrast, a standard rank-1 SVD fails to scale efficiently as the matrix size increases.

Key Results

The effectiveness of these reorganization techniques was validated across diverse datasets:

  • Image Compression: A rank-4 tiled approximation using only 10,000 parameters was found to be visually and quantitatively superior to a rank-25 standard SVD requiring 25,000 parameters.
  • Large-Scale Validation: In a study of over 48,000 images from ImageNet, the tiled approach outperformed the traditional SVD in 98.6% of cases when targeting a 5% or 10% relative error.
  • Temporal Accuracy: Reshaping COVID-19 positivity rate data (50 states over 150 days) from a $50 \times 150$ matrix to a $150 \times 50$ matrix reduced reconstruction error from 6.7% to 2.7% using the same number of parameters (300).
Figure 5: The original high-resolution image used as a reference for evaluating compression performance.

Discussion and Limitations

The "best" approximation provided by the SVD is local to the matrix structure. Tiling and reshaping act as "model priors," guiding the SVD to exploit physical realities like spatial locality or piecewise temporal trends.

However, challenges remain. There is currently no automated algorithm to determine the optimal shape for an arbitrary dataset. Additionally, while tiling shows massive gains on ImageNet, some of this improvement may be influenced by existing JPEG artifacts in the source data, which are themselves tile-based. Future work will explore more exotic reshaping techniques beyond the Kronecker model.

Conclusion

The Eckart-Young theorem is not the end of the story for low-rank approximation. By rethinking data organization, researchers can unlock significant gains in compression and accuracy, proving that the "best" standard SVD is often just a starting point.

Summary updated

Abstract

The Eckhart-Young theorem states that the best low-rank approximation of a matrix can be constructed from the leading singular values and vectors of the matrix. Here, we illustrate that the practical implications of this result crucially depend on the organization of the matrix data. In particular, we will show examples where a rank 2 approximation of the matrix data in a different representation more accurately represents the entire matrix than a rank 5 approximation of the original matrix data -- even though both approximations have the same number of underlying parameters. Beyond images, we show examples of how flexible orientation enables better approximation of time series data, which suggests additional applicability of the findings. Finally, we conclude with a theoretical result that the effect of data organization can result in an unbounded improvement to the matrix approximation factor as the matrix dimension grows.
BibTeX
@misc{gleich2024better,
  author = {David F. Gleich},
  title = {{Better than best low-rank approximation with the singular value decomposition}},
  year = {2024},
  eprint = {2402.18427},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.18427},
}
Figure