Optimal Algorithms for <formula formulatype="inline"> <tex Notation="TeX">L_{1}</tex></formula>-subspace Signal Processing

DOI10.1109/TSP.2014.2338077MaRDI QIDQ4579476zbMATH OpenOpenAlexWikidataFDO

Authors Panos P. Markopoulos, George N. Karystinos, Dimitris A. Pados

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.6785

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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 $NgeqD$, we present an optimal algorithm of complexity $mathcalO(N^D)$. We generalize to multiple $L_1$-max-projection components and present an explicit optimal $L_1$ subspace calculation algorithm of complexity $mathcalO(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.

Cited in

(13)

• Suboptimal selecting subspace for biorthonormal signal representation
• Multiple sparse measurement gradient reconstruction algorithm for DOA estimation in compressed sensing
• On the robust PCA and Weiszfeld's algorithm
• F-norm distance metric based robust 2DPCA and face recognition
• Principal component analysis with drop rank covariance matrix
• On computational aspects of certain optimal digital signal processing algorithms
• Optimization for L₁-Norm Error Fitting via Data Aggregation
• ISLET: fast and optimal low-rank tensor regression via importance sketching
• Avoiding optimal mean \(\ell_{2,1}\)-norm maximization-based robust PCA for reconstruction
• Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for \(\boldsymbol{\ell_1}\) -Norm Principal Component Analysis
• Particularities and commonalities of singular spectrum analysis as a method of time series analysis and signal processing
• Optimization on the quaternion Stiefel manifold with applications. II: L1-QPCA
• Efficient Bayesian inference on Grassmann manifolds leveraging Lagrangian Hamiltonian Monte Carlo

This page was built for publication: Optimal Algorithms for <formula formulatype="inline"> <tex Notation="TeX">$L_{1}$</tex></formula>-subspace Signal Processing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4579476)