Optimal Algorithms for $L_1$-subspace Signal Processing

Abstract

We describe ways to define and calculate $L_1$-norm signal subspaces which are less sensitive to outlying data than $L_2$-calculated subspaces. We start with the computation of the $L_1$ maximum-projection principal component of a data matrix containing $N$ signal samples of dimension $D$. We show that while the general problem is formally NP-hard in asymptotically large $N$, $D$, the case of engineering interest of fixed dimension $D$ and asymptotically large sample size $N$ is not. In particular, for the case where the sample size is less than the fixed dimension ($N<D$), we present in explicit form an optimal algorithm of computational cost $2^N$. For the case $N\ge D$, we present an optimal algorithm of complexity $\mathcal{O}(N^D)$. We generalize to multiple $L_1$-max-projection components and present an explicit optimal $L_1$ subspace calculation algorithm of complexity $\mathcal{O}(N^{DK-K+1})$ where $K$ is the desired number of $L_1$ principal components (subspace rank). We conclude with illustrations of $L_1$-subspace signal processing in the fields of data dimensionality reduction, direction-of-arrival estimation, and image conditioning/restoration.

References in corpus (1)

• Two Proposals for Robust PCA using Semidefinite Programming

Cited by in corpus (17)

• Efficient L1-Norm Principal-Component Analysis via Bit Flipping
• An Overview of Robust Subspace Recovery
• Particularities and commonalities of singular spectrum analysis as a method of time series analysis and signal processing
• L1-norm Principal-Component Analysis of Complex Data
• A Simple and Fast Algorithm for L1-norm Kernel PCA
• The Exact Solution to Rank-1 L1-norm TUCKER2 Decomposition
• Iteratively Reweighted Least Squares Algorithms for L1-Norm Principal Component Analysis
• Timescales of Chaos in the Inner Solar System: Lyapunov Spectrum and Quasi-integrals of Motion
• Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
• Robust Subspace Recovery with Adversarial Outliers
• A randomized algorithm for enumerating zonotope vertices
• Optimization for L1-Norm Error Fitting via Data Aggregation
• Outlier Detection and Data Clustering via Innovation Search
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants
• Optimal ${\ell }_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation
• Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for ${\ell }_1$-Norm Principal Component Analysis