L1-norm principal component analysis

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

${\displaystyle {\begin{aligned}&{\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{aligned}}}$

(1)

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

${\displaystyle {\begin{aligned}&{\underset {\mathbf {q} \in \mathbb {R} ^{D\times 1}}{\max }}~~\|\mathbf {X} ^{\top }\mathbf {q} \|_{1}\\&{\text{subject to}}~~\|\mathbf {q} \|_{2}=1.\end{aligned}}}$

(2)

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

The maximization metric in (2) can be expanded as

${\displaystyle \|\mathbf {X} ^{\top }\mathbf {Q} \|_{1}=\sum _{k=1}^{K}\sum _{n=1}^{N}|\mathbf {x} _{n}^{\top }\mathbf {q} _{k}|.}$

(3)

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

${\displaystyle {\begin{aligned}\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{aligned}}}$

(4)

Procrustes Theorem[13][14] states that if ${\displaystyle \mathbf {A} }$ has SVD ${\displaystyle \mathbf {U} _{m\times n}{\boldsymbol {\Sigma }}_{n\times n}\mathbf {V} _{n\times n}^{\top }}$, then ${\displaystyle \Phi (\mathbf {A} )=\mathbf {U} \mathbf {V} ^{\top }}$.

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

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

(5)

then

${\displaystyle {\begin{aligned}\mathbf {Q} _{\text{L1}}=\Phi (\mathbf {X} \mathbf {B} _{\text{BNM}})\end{aligned}}}$

(6)

is the exact solution to L1-PCA in (2). The nuclear-norm ${\displaystyle \|\cdot \|_{*}}$ in (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, ${\displaystyle \mathbf {Q} _{\text{L1}}}$, the solution to BNM can be obtained as

${\displaystyle {\begin{aligned}\mathbf {B} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}})\end{aligned}}}$

(7)

where ${\displaystyle {\text{sgn}}(\cdot )}$ returns the ${\displaystyle \{\pm 1\}}$-sign matrix of its matrix argument (with no loss of generality, we can consider ${\displaystyle {\text{sgn}}(0)=1}$). In addition, it follows that ${\displaystyle \|\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {B} _{\text{BNM}}\|_{*}}$. BNM in (5) is a combinatorial problem over antipodal binary variables. Therefore, its exact solution can be found through exhaustive evaluation of all ${\displaystyle 2^{NK}}$ elements of its feasibility set, with asymptotic cost ${\displaystyle {\mathcal {O}}(2^{NK})}$. Therefore, L1-PCA can also be solved, through BNM, with cost ${\displaystyle {\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 ${\displaystyle N}$ for fixed data dimension ${\displaystyle D}$, ${\displaystyle {\mathcal {O}}(N^{rK-K+1})}$.[1]

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

${\displaystyle {\begin{aligned}&{\underset {\mathbf {b} \in \{\pm 1\}^{N\times 1}}{\text{max}}}~~\mathbf {b} ^{\top }\mathbf {X} ^{\top }\mathbf {X} \mathbf {b} .\end{aligned}}}$

(8)

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

${\displaystyle {\begin{aligned}\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{aligned}}}$

(9)

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

L1-PCA has also been generalized to process complex data. For complex L1-PCA, two efficient algorithms were proposed in 2018.[19]

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.[20] Two algorithms for the solution of L1-Tucker are L1-HOSVD and L1-HOOI.[20][21][22]

MATLAB code for L1-PCA is available at MathWorks[23] and other repositories.[18]