L1-norm principal component analysis

Consider any matrix $\backslash mathbf\; X\; =\; [\backslash mathbf\; x\_1,\; \backslash mathbf\; x\_2,\; \backslash ldots,\; \backslash mathbf\; x\_N]\; \backslash in\; \backslash mathbb\; R^\{D\; \backslash times\; N\}$ consisting of $N$ $D$-dimensional data points. Define $r=rank(\backslash mathbf\; X)$. For integer $K$ such that , L1-PCA is formulated as:

{{NumBlk|:|

\begin{align}

&\underset{\mathbf Q=[\mathbf q_1, \mathbf q_2, \ldots, \mathbf q_K] \in \mathbb R^{D \times K}}{\max}~~\| \mathbf X^\top \mathbf Q\|_1\\

&\text{subject to}~~ \mathbf Q^\top \mathbf Q=\mathbf I_K.

\end{align}

|{{EquationRef|1}}}}

For $K=1$, ({{EquationNote|1}}) simplifies to finding the L1-norm principal component (L1-PC) of $\backslash mathbf\; X$ by

{{NumBlk|:|

\begin{align}

&\underset{\mathbf q \in \mathbb R^{D \times 1}}{\max}~~\| \mathbf X^\top \mathbf q\|_1\\

&\text{subject to}~~ \| \mathbf q\|_2 =1.

\end{align}

|{{EquationRef|2}}}}

In ({{EquationNote|1}})-({{EquationNote|2}}), L1-norm $\backslash |\; \backslash cdot\; \backslash |\_1$ returns the sum of the absolute entries of its argument and L2-norm $\backslash |\; \backslash cdot\; \backslash |\_2$ returns the sum of the squared entries of its argument. If one substitutes $\backslash |\; \backslash cdot\; \backslash |\_1$ in ({{EquationNote|2}}) by the Frobenius/L2-norm $\backslash |\; \backslash cdot\; \backslash |\_F$, then the problem becomes standard PCA and it is solved by the matrix $\backslash mathbf\; Q$ that contains the $K$ dominant singular vectors of $\backslash mathbf\; X$ (i.e., the singular vectors that correspond to the $K$ highest singular values).

The maximization metric in ({{EquationNote|2}}) can be expanded as

{{NumBlk|:|

$\backslash |\; \backslash mathbf\; X^\backslash top\; \backslash mathbf\; Q\backslash |\_1=\backslash sum\_\{k=1\}^K\; \backslash sum\_\{n=1\}^N\; |\backslash mathbf\; x\_n^\backslash top\; \backslash mathbf\; q\_k|.$

|{{EquationRef|3}}}}

For any matrix $\backslash mathbf\; A\; \backslash in\; \backslash mathbb\; R^\{m\; \backslash times\; n\}$ with $m\; \backslash geq\; n$, define $\backslash Phi(\backslash mathbf\; A)$ as the nearest (in the L2-norm sense) matrix to $\backslash mathbf\; A$ that has orthonormal columns. That is, define

{{NumBlk|:|

\begin{align}

\Phi(\mathbf A) = & \underset{\mathbf Q \in \mathbb R^{m \times n}}{\text{argmin}}~~\| \mathbf A - \mathbf Q\|_F\\

&\text{subject to}~~ \mathbf Q^\top \mathbf Q=\mathbf I_n.

\end{align}

|{{EquationRef|4}}}}

Procrustes Theorem{{cite journal|last1=Eldén|first1=Lars|last2=Park|first2=Haesun|title=A Procrustes problem on the Stiefel manifold|journal=Numerische Mathematik|date=1 June 1999|volume=82|issue=4|pages=599–619|doi=10.1007/s002110050432|citeseerx=10.1.1.54.3580|s2cid=206895591}}{{cite journal|last1=Schönemann|first1=Peter H.|title=A generalized solution of the orthogonal procrustes problem|journal=Psychometrika|date=March 1966|volume=31|issue=1|pages=1–10|doi=10.1007/BF02289451|hdl=10338.dmlcz/103138|s2cid=121676935|hdl-access=free}} states that if $\backslash mathbf\; A$ has SVD $\backslash mathbf\; U\_\{m\; \backslash times\; n\}\; \backslash boldsymbol\; \backslash Sigma\_\{n\; \backslash times\; n\}\; \backslash mathbf\; V\_\{n\; \backslash times\; n\}^\backslash top$, then

$\backslash Phi(\backslash mathbf\; A)=\backslash mathbf\; U\; \backslash mathbf\; V^\backslash top$.

Markopoulos, Karystinos, and Pados showed that, if $\backslash mathbf\; B\_\{\backslash text\{BNM\}\}$ is the exact solution to the binary nuclear-norm maximization (BNM) problem

{{NumBlk|:|

\begin{align}

\underset{\mathbf B \in \{ \pm 1\}^{N \times K}}{\text{max}}~~\| \mathbf X \mathbf B\|_*^2,

\end{align}

|{{EquationRef|5}}}}

then

{{NumBlk|:|

\begin{align}

\mathbf Q_{\text{L1}} = \Phi(\mathbf X\mathbf B_{\text{BNM}})

\end{align}

|{{EquationRef|6}}}}

is the exact solution to L1-PCA in ({{EquationNote|2}}). The nuclear-norm $\backslash |\; \backslash cdot\; \backslash |\_*$ in ({{EquationNote|2}}) returns the summation of the singular values of its matrix argument and can be calculated by means of standard SVD. Moreover, it holds that, given the solution to L1-PCA, $\backslash mathbf\; Q\_\{\backslash text\{L1\}\}$, the solution to BNM can be obtained as

{{NumBlk|:|

\begin{align}

\mathbf B_{\text{BNM}} = \text{sgn}(\mathbf X^\top \mathbf Q_{\text{L1}})

\end{align}

|{{EquationRef|7}}}}

where $\backslash text\{sgn\}(\backslash cdot)$ returns the $\backslash \{\backslash pm\; 1\backslash \}$-sign matrix of its matrix argument (with no loss of generality, we can consider $\backslash text\{sgn\}(0)=1$). In addition, it follows that $\backslash |\; \backslash mathbf\; X^\backslash top\; \backslash mathbf\; Q\_\{\backslash text\{L1\}\}\backslash |\_1\; =\; \backslash |\; \backslash mathbf\; X\; \backslash mathbf\; B\_\{\backslash text\{BNM\}\}\backslash |\_*$. BNM in ({{EquationNote|5}}) is a combinatorial problem over antipodal binary variables. Therefore, its exact solution can be found through exhaustive evaluation of all $2^\{NK\}$ elements of its feasibility set, with asymptotic cost $\backslash mathcal\; O(2^\{NK\})$. Therefore, L1-PCA can also be solved, through BNM, with cost $\backslash mathcal\; O(2^\{NK\})$ (exponential in the product of the number of data points with the number of the sought-after components). It turns out that L1-PCA can be solved optimally (exactly) with polynomial complexity in $N$ for fixed data dimension $D$, $\backslash mathcal\{O\}(N^\{rK-K+1\})$.

For the special case of $K=1$ (single L1-PC of $\backslash mathbf\; X$), BNM takes the binary-quadratic-maximization (BQM) form

{{NumBlk|:|

\begin{align}

& \underset{\mathbf b \in \{ \pm 1\}^{N \times 1}}{\text{max}}~~ \mathbf b^\top \mathbf X^\top \mathbf X \mathbf b.

\end{align}

|{{EquationRef|8}}}}

The transition from ({{EquationNote|5}}) to ({{EquationNote|8}}) for $K=1$ holds true, since the unique singular value of $\backslash mathbf\; X\; \backslash mathbf\; b$ is equal to $\backslash |\; \backslash mathbf\; X\; \backslash mathbf\; b\backslash |\_2\; =\; \backslash sqrt\{\backslash mathbf\; b^\backslash top\; \backslash mathbf\; X^\backslash top\; \backslash mathbf\; X\; \backslash mathbf\; b\}$, for every $\backslash mathbf\; b$. Then, if $\backslash mathbf\; b\_\{\backslash text\{BNM\}\}$ is the solution to BQM in ({{EquationNote|7}}), it holds that

{{NumBlk|:|

\begin{align}

\mathbf q_{\text{L1}} = \Phi(\mathbf X \mathbf b_{\text{BNM}}) = \frac{\mathbf X \mathbf b_{\text{BNM}}}{\| \mathbf X \mathbf b_{\text{BNM}}\|_2}

\end{align}

|{{EquationRef|9}}}}

is the exact L1-PC of $\backslash mathbf\; X$, as defined in ({{EquationNote|1}}). In addition, it holds that $\backslash mathbf\; b\_\{\backslash text\{BNM\}\}\; =\; \backslash text\{sgn\}(\backslash mathbf\; X^\backslash top\; \backslash mathbf\; q\_\{\backslash text\{L1\}\})$ and $\backslash |\; \backslash mathbf\; X^\backslash top\; \backslash mathbf\; q\_\{\backslash text\{L1\}\}\backslash |\_1\; =\; \backslash |\; \backslash mathbf\; X\; \backslash mathbf\; b\_\{\backslash text\{BNM\}\}\backslash |\_2$.

As shown above, the exact solution to L1-PCA can be obtained by the following two-step process:

1. Solve the problem in ({{EquationNote|5}}) to obtain $\backslash mathbf\; B\_\{\backslash text\{BNM\}\}$.

2. Apply SVD on $\backslash mathbf\; X\backslash mathbf\; B\_\{\backslash text\{BNM\}\}$ to obtain $\backslash mathbf\; Q\_\{\backslash text\{L1\}\}$.

BNM in ({{EquationNote|5}}) can be solved by exhaustive search over the domain of $\backslash mathbf\; B$ with cost $\backslash mathcal\{O\}(2^\{NK\})$.

Also, L1-PCA can be solved optimally with cost $\backslash mathcal\{O\}(N^\{rK-K+1\})$, when $r=rank(\backslash mathbf\; X)$ is constant with respect to $N$ (always true for finite data dimension $D$).{{cite book|last1=Markopoulos|first1=PP|last2=Kundu|first2=S|last3=Chamadia|first3=S|last4=Tsagkarakis|first4=N|last5=Pados|first5=DA|title=Advances in Principal Component Analysis |chapter=Outlier-Resistant Data Processing with L1-Norm Principal Component Analysis |date=2018|issue=Springer, Singapore|pages=121–135|doi=10.1007/978-981-10-6704-4_6|isbn=978-981-10-6703-7}}

In 2008, Kwak proposed an iterative algorithm for the approximate solution of L1-PCA for $K=1$. This iterative method was later generalized for $K>1$ components.{{cite journal|last1=Nie|first1=F|last2=Huang|first2=H|last3=Ding|first3=C|last4=Luo|first4=Dijun|last5=Wang|first5=H|title=Robust principal component analysis with non-greedy l1-norm maximization|journal=22nd International Joint Conference on Artificial Intelligence|date=July 2011|pages=1433–1438}} Another approximate efficient solver was proposed by McCoy and Tropp{{cite journal|last1=McCoy|first1=Michael|last2=Tropp|first2=Joel A.|date=2011|title=Two proposals for robust PCA using semidefinite programming|journal=Electronic Journal of Statistics|volume=5|pages=1123–1160|doi=10.1214/11-EJS636|arxiv=1012.1086|s2cid=14102421}} by means of semi-definite programming (SDP). Most recently, L1-PCA (and BNM in ({{EquationNote|5}})) were solved efficiently by means of bit-flipping iterations (L1-BF algorithm).

1 function L1BF($\backslash mathbf\; X$, $K$):

2 Initialize $\backslash mathbf\; B^\{(0)\}\; \backslash in\; \backslash \{\backslash pm\; 1\backslash \}^\{N\; \backslash times\; K\}$ and $\backslash mathcal\; L\; \backslash leftarrow\; \backslash \{1,2,\backslash ldots,\; NK\backslash \}$

3 Set $t\; \backslash leftarrow\; 0$ and $\backslash omega\; \backslash leftarrow\; \backslash |\; \backslash mathbf\; X\; \backslash mathbf\; B^\{(0)\}\; \backslash |\_*$

4 Until termination (or $T$ iterations)

5 $\backslash mathbf\; B\; \backslash leftarrow\; \backslash mathbf\; B^\{(t)\}$, $t\text{'}\; \backslash leftarrow\; t$

6 For $x\; \backslash in\; \backslash mathcal\; L$

7 $k\; \backslash leftarrow\; \backslash lceil\; \backslash frac\{x\}\{N\}\; \backslash rceil$, $n\; \backslash leftarrow\; x-N(k-1)$

8 $[\backslash mathbf\; B]\_\{n,k\}\; \backslash leftarrow\; -\; [\backslash mathbf\; B]\_\{n,k\}$ // flip bit

9 $a(n,k)\; \backslash leftarrow\; \backslash |\; \backslash mathbf\; X\; \backslash mathbf\; B\; \backslash |\_*$ // calculated by SVD or faster (see)

10 if $a(n,k)>\backslash omega$

11 $\backslash mathbf\; B^\{(t)\}\; \backslash leftarrow\; \backslash mathbf\; B$, $t\text{'}\; \backslash leftarrow\; t+1$

12 $\backslash omega\; \backslash leftarrow\; a(n,k)$

13 end

14 if $t\text{'}=t$ // no bit was flipped

15 if $\backslash mathcal\; L\; =\; \backslash \{1,2,\; \backslash ldots,\; NK\backslash \}$

16 terminate

17 else

18 $\backslash mathcal\; L\; \backslash leftarrow\; \backslash \{1,2,\; \backslash ldots,\; NK\backslash \}$

The computational cost of L1-BF is $\backslash mathcal\; O\; (ND\; min\backslash \{N,D\backslash \}\; +\; N^2K^2(K^2\; +\; r))$.

L1-PCA has also been generalized to process complex data. For complex L1-PCA, two efficient algorithms were proposed in 2018.{{cite journal|last1=Tsagkarakis|first1=Nicholas|last2=Markopoulos|first2=Panos P.|last3=Sklivanitis|first3=George|last4=Pados|first4=Dimitris A.|title=L1-Norm Principal-Component Analysis of Complex Data|journal=IEEE Transactions on Signal Processing|date=15 June 2018|volume=66|issue=12|pages=3256–3267|doi=10.1109/TSP.2018.2821641|arxiv=1708.01249|bibcode=2018ITSP...66.3256T|s2cid=21011653}}

L1-PCA has also been extended for the analysis of tensor data, in the form of L1-Tucker, the L1-norm robust analogous of standard Tucker decomposition.{{cite journal|last1=Chachlakis|first1=Dimitris G.|last2=Prater-Bennette|first2=Ashley|last3=Markopoulos|first3=Panos P.|title=L1-norm Tucker Tensor Decomposition|journal=IEEE Access|date=22 November 2019|volume=7|pages=178454–178465|doi=10.1109/ACCESS.2019.2955134|arxiv=1904.06455|doi-access=free}} Two algorithms for the solution of L1-Tucker are L1-HOSVD and L1-HOOI.{{cite book|last1=Markopoulos|first1=Panos P.|last2=Chachlakis|first2=Dimitris G.|last3=Prater-Bennette|first3=Ashley|title=2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP) |chapter=L1-Norm Higher-Order Singular-Value Decomposition |date=21 February 2019|pages=1353–1357|doi=10.1109/GlobalSIP.2018.8646385|isbn=978-1-7281-1295-4|s2cid=67874182}}{{cite journal|last1=Markopoulos|first1=Panos P.|last2=Chachlakis|first2=Dimitris G.|last3=Papalexakis|first3=Evangelos|title=The Exact Solution to Rank-1 L1-Norm TUCKER2 Decomposition

|journal=IEEE Signal Processing Letters|volume=25|issue=4|date=April 2018|pages=511–515|doi=10.1109/LSP.2018.2790901|arxiv=1710.11306|bibcode=2018ISPL...25..511M|s2cid=3693326}}

MATLAB code for L1-PCA is available at MathWorks.{{cite web|title=L1-PCA TOOLBOX|url=https://www.mathworks.com/matlabcentral/fileexchange/64855-l1-pca-toolbox|access-date=May 21, 2018}}

{{reflist}}

Category:Data analysis