Optimal sparse L1-norm principal-component analysis
Shubham Chamadia, Dimitris A. Pados
Abstract
We present an algorithm that computes exactly (optimally) the S-sparse (1≤S<;D) maximum-L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -norm-projection principal component of a real-valued data matrix X ∈ ℝ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D×N</sup> that contains N samples of dimension D. For fixed sample support N, the optimal L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -sparse algorithm has linear complexity in data dimension, O(D). For fixed dimension D (thus, fixed sparsity S), the optimal L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -sparse algorithm has polynomial complexity in sample support, O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</sup> ). Numerical studies included in this paper illustrate the theoretical developments and demonstrate the remarkable robustness to faulty data/measurements of the calculated sparse-L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> principal components.
BibTeX
@inproceedings{icassp2017_optimalsparsel1n,
title = {Optimal sparse L1-norm principal-component analysis},
author = {Shubham Chamadia and Dimitris A. Pados},
booktitle = {ICASSP 2017},
year = {2017}
}