Low-Rank Principal Eigenmatrix Analysis

Krishna Balasubramanian, Elynn Y. Chen, Jianqing Fan, Xiang WuarXiv 2019 · arXiv

Abstract

Traditional Principal Component Analysis (PCA) often fails in high-dimensional regimes where the number of features significantly exceeds the sample size. While Sparse PCA addresses this by assuming sparsity, many real-world signals are dense yet structured. This paper introduces Low-Rank Principal Eigenmatrix Analysis, a framework that leverages the low-rank structure of reshaped eigenvectors. We present the SMART-PM algorithm, which achieves minimax optimal estimation error by regularizing the "eigenmatrix" rank, providing a robust alternative for data with underlying circulant or Toeplitz regularities.

Introduction: The Limits of Sparsity

Principal Component Analysis (PCA) is fundamental to dimensionality reduction, yet it encounters a "curse of dimensionality" when the feature count $d$ is much larger than the sample size $n$. In such cases, the sample covariance matrix is a poor estimator of the true population covariance.

To combat this, Sparse PCA has become the standard remedy, assuming that only a small subset of features contributes to the principal component. However, in fields like signal processing, medical imaging, or finance, eigenvectors are often dense—meaning most entries are non-zero—but they possess an inherent structural regularity. This paper proposes that instead of sparsity, we should look for a low-rank structure in the "eigenmatrix"—the eigenvector reshaped into a 2D grid.

The SMART-PM Framework

The authors propose finding a unit vector that maximizes the quadratic form while constraining its "matricized" version to a maximum rank $k$. To solve this, they introduce SMART-PM (Sequentially MATricized Rank Truncated-Power Method).

The algorithm iterates through four key steps:

  1. Power Step: Standard matrix-vector multiplication.
  2. Matricization: Reshaping the $d$-dimensional vector into a $p \times p$ matrix (where $d = p^2$).
  3. Rank Truncation: Using Singular Value Decomposition (SVD) to retain only the top $k$ singular values, enforcing the low-rank constraint.
  4. Vectorization & Normalization: Reverting the matrix to a vector and normalizing it.

The Matricization Trick

The "aha moment" of this research is that complex, dense vectors often reveal a simple, low-rank structure when their geometry is changed. For example, the top eigenvector of a circulant matrix becomes a rank-1 matrix when reshaped correctly.

Singular value spectra of reshaped eigenvectors across different covariance structures.

As shown in the figure above, the singular values of these "eigenmatrices" often decay rapidly. By projecting onto the space of low-rank matrices, SMART-PM effectively filters out high-rank noise, which is prevalent in high-dimensional "spiked" covariance models. This approach is agnostic to sparsity, making it more robust for applications where signals are dense but regular.

Experimental Results and Insights

The method was evaluated using synthetic datasets with Toeplitz, Circulant, and Kronecker product structures. Key findings include:

  • Superior Estimation: SMART-PM significantly reduced estimation error compared to the vanilla power method in structured settings.
  • Sample Efficiency: The method achieves the minimax lower bound for estimation error, indicating it is as statistically efficient as theoretically possible.
  • Initialization and Convergence: While the problem is non-convex, the authors prove geometric convergence under specific conditions. Initializing with the "Maximum Eigenmatrix" of the sample covariance was found to be particularly effective.

Conclusion and Future Directions

Low-Rank Principal Eigenmatrix Analysis provides a powerful alternative to Sparse PCA by capturing structural regularity rather than just feature importance. While the current method requires knowing the correct reshaping dimensions, future work aims to explore Tensorization (reshaping into higher-dimensional arrays) and automated methods to discover the optimal data permutations for low-rank representation.

Summary updated

Abstract

Sparse PCA is a widely used technique for high-dimensional data analysis. In this paper, we propose a new method called low-rank principal eigenmatrix analysis. Different from sparse PCA, the dominant eigenvectors are allowed to be dense but are assumed to have a low-rank structure when matricized appropriately. Such a structure arises naturally in several practical cases: Indeed the top eigenvector of a circulant matrix, when matricized appropriately is a rank-1 matrix. We propose a matricized rank-truncated power method that could be efficiently implemented and establish its computational and statistical properties. Extensive experiments on several synthetic data sets demonstrate the competitive empirical performance of our method.
BibTeX
@misc{balasubramanian2019low,
  author = {Krishna Balasubramanian and Elynn Y. Chen and Jianqing Fan and Xiang Wu},
  title = {{Low-Rank Principal Eigenmatrix Analysis}},
  year = {2019},
  eprint = {1904.12369},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.12369},
}
Figure