Optimal sparse L1-norm principal-component analysis

摘要

We present an algorithm that computes exactly (optimally) the S-sparse (1≤S<;D) maximum-L-norm-projection principal component of a real-valued data matrix X ∈ ℝ that contains N samples of dimension D. For fixed sample support N, the optimal L-sparse algorithm has linear complexity in data dimension, O(D). For fixed dimension D (thus, fixed sparsity S), the optimal L-sparse algorithm has polynomial complexity in sample support, O(N). Numerical studies included in this paper illustrate the theoretical developments and demonstrate the remarkable robustness to faulty data/measurements of the calculated sparse-L principal components.