Panos Markopoulos

## Software

### MATLAB SOFTWARE FOR L1-PCA

##### Problem Definition

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:

\text{PCA}:~~~~~~\underset{\mathbf{Q} \in \mathbb R^{D \times K}; ~\mathbf Q^T \mathbf Q = \mathbf I_{K}}{\text{maximize}} ~ \| \mathbf Q^\top \mathbf X\|_F

and is solved through Singular-Value Decomposition (SVD) of $\mathbf X$. L1-norm Principal-Component Analysis (L1-PCA) is defined as:

\text{L1-PCA}:~~~~\underset{\mathbf{Q} \in \mathbb R^{D \times K}; ~\mathbf Q^T \mathbf Q = \mathbf I_{K}}{\text{maximize}} ~ \| \mathbf Q^\top \mathbf X\|_1.

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.