Recovering PCA from Hybrid-$(\ell_1,\ell_2)$ Sparse Sampling of Data Elements
This work addresses data recovery from sparse samples for applications in machine learning and data analysis, presenting an incremental improvement over existing sampling methods.
The paper tackles the problem of recovering a data matrix from a few of its elements by proposing a randomized algorithm that sparsifies data using hybrid-($\\ell_1,\\ell_2$) sampling, which combines $\\ell_2$ and $\\ell_1$ sampling to achieve near-PCA reconstruction from a sublinear sample-size and outperforms individual $\\ell_1$ or $\\ell_2$ methods.
This paper addresses how well we can recover a data matrix when only given a few of its elements. We present a randomized algorithm that element-wise sparsifies the data, retaining only a few its elements. Our new algorithm independently samples the data using sampling probabilities that depend on both the squares ($\ell_2$ sampling) and absolute values ($\ell_1$ sampling) of the entries. We prove that the hybrid algorithm recovers a near-PCA reconstruction of the data from a sublinear sample-size: hybrid-($\ell_1,\ell_2$) inherits the $\ell_2$-ability to sample the important elements as well as the regularization properties of $\ell_1$ sampling, and gives strictly better performance than either $\ell_1$ or $\ell_2$ on their own. We also give a one-pass version of our algorithm and show experiments to corroborate the theory.