Consider data matrix $\mathbf X =[\mathbf x_{1}, \ldots, \mathbf x_{N}] \in \mathbb R^{D \times N}$ (i.e., N D-dimensional points) and some K $\leq$ D. Standard (or L2-norm) Principal-Component Analysis (PCA) is defined as:
L1-PCA has demonstrated in several applications: (a) very similar performance to standard PCA when applied on outlier-free data and (b) significant resistance to outliers when the data are corrupted.
Performance Example
The following Matlab scripts implement algorithms that solve L1-PCA exactly, or approximately.
Exhaustive-search L1-PCA
Returns: K ≥ 1 L1-PCs (exact solution).
Method: Exhaustive search over entire binary field.
Complexity: Exponential in N and K; linear in D. References
P. P. Markopoulos, G. N. Karystinos, and D. A. Pados,
Optimal algorithms for L1-subspace signal processing,
IEEE Transactions on Signal Processing, vol. 62, pp. 5046-5058, October 2014.
P. P. Markopoulos, G. N. Karystinos, and D. A. Pados,
Some options for L1-subspace signal processing,
in Proc. IEEE International Symposium on Wireless Communication Systems (IEEE ISWCS 2013), Ilmenau, Germany, August 2013, pp. 622-626.
P. P. Markopoulos, N. Tsagkarakis, D. A. Pados, and G. N. Karystinos,
Direction-of-arrival estimation from L1-norm principal components,
in Proc. IEEE International Symposium on Phased Array Systems and Technology (IEEE PAST 2016), Boston, MA, October 2016, pp. 1-6.
Polynomial L1-PCA
Returns: K ≥ 1 L1-PCs (exact solution).
Method: Polynomial search over subset of binary field.
Complexity: Polynomial in N; exponential in d and K (for fixed d w.r.t. N)
References
P. P. Markopoulos, G. N. Karystinos, and D. A. Pados,
Optimal algorithms for L1-subspace signal processing,
IEEE Transactions on Signal Processing, vol. 62, pp. 5046-5058, October 2014.
P. P. Markopoulos, G. N. Karystinos, and D. A. Pados,
Some options for L1-subspace signal processing,
in Proc. IEEE International Symposium on Wireless Communication Systems (IEEE ISWCS 2013), Ilmenau, Germany, August 2013, pp. 622-626.
P. P. Markopoulos, N. Tsagkarakis, D. A. Pados, and G. N. Karystinos,
Direction-of-arrival estimation from L1-norm principal components,
in Proc. IEEE International Symposium on Phased Array Systems and Technology (IEEE PAST 2016), Boston, MA, October 2016, pp. 1-6.
L1-BF (L1-PCA by bit-flipping)
Returns: K ≥ 1 L1-PCs (approximate solution).
Method: Single-bit Flipping.
Complexity: Quadratic in N; at most quadratic in D; at most quadratic in K; linear in d.
References
P. P. Markopoulos, S. Kundu, S. Chamadia, and D. A. Pados,
Efficient L1-norm Principal-Component Analysis via bit flipping,
IEEE Transactions on Signal Processing, vol. 65, pp. 4252-4264, August 2017.
P. P. Markopoulos, S. Kundu, S. Chamadia, and D. A. Pados,
L1-norm Principal-Component Analysis via bit flipping,
in Proc. IEEE International Conference on Machine Learning and Applications (IEEE ICMLA 2016), Anaheim, CA, December 2016, pp. 326-332.
S. Kundu, P. P. Markopoulos, and D. A. Pados,
Fast computation of the L1-principal component of real-valued data,
in Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (IEEE ICASSP 2014), Florence, Italy, May 2014, pp. 8028-8032.
P. P. Markopoulos, G. N. Karystinos, and D. A. Pados,
Optimal algorithms for L1-subspace signal processing,
IEEE Transactions on Signal Processing, vol. 62, pp. 5046-5058, October 2014.
P. P. Markopoulos, G. N. Karystinos, and D. A. Pados,
Some options for L1-subspace signal processing,
in Proc. IEEE International Symposium on Wireless Communication Systems (IEEE ISWCS 2013), Ilmenau, Germany, August 2013, pp. 622-626.
MATLAB SOFTWARE FOR L1-TUCKER2 (3-WAY TENSORS)
The following Matlab script solves rank-1 L1-TUCKER2 exactly.
Exhaustive-search L1-TUCKER2
Returns: Rank-1 PCs of (D by M by N) tensor.
Method: Exhaustive search over entire binary field.
Complexity: Exponential in N; linear in D and M. References
P. P. Markopoulos, D. G. Chachlakis, and E. E. Papalexakis,
The exact solution to rank-1 L1-norm TUCKER2 decomposition,
IEEE Signal Processing Letters, Jan. 2018.
Efficient L1-TUCKER2 (SPIE paper)
Returns: Rank-K PCs of (D by M by N) tensor.
Method: Alternating maximization.
Complexity: Linear in D, M, N; quadratic in K; linear in number of iterations. References
P. P. Markopoulos, D. G. Chachlakis, and E. E. Papalexakis,
The exact solution to rank-1 L1-norm TUCKER2 decomposition,
IEEE Signal Processing Letters, Jan. 2018.
D. G. Chachlakis and P. P. Markopoulos,
Robust decomposition of 3-way tensors based on L1-norm,
in Proc. SPIE Defense and Commercial Sensing (SPIE DCS 2018), Orlando, FL, Apr. 2018.