Randomized Subspace Learning Approach For High Dimensional Low Rank Plus Sparse Matrix Decomposition

Abstract

In this paper, a randomized algorithm for high dimensional low rank plus sparse matrix decomposition is proposed. Existing decomposition methods are not scalable to big data since they rely on using the whole data to extract the low-rank/sparse components, and are based on an optimization problem whose dimensionality is equal to the dimension of the given data. We reformulate the low rank plus sparse matrix decomposition problem as a column-row subspace learning problem. It is shown that when the column/row subspace of the low rank matrix is incoherent with the standard basis, the column/row subspace can be obtained from a small random subset of the columns/rows of the given data matrix. Thus, the high dimensional matrix decomposition problem is converted to a subspace learning problem, which is a low-dimensional optimization problem, and the proposed method uses a small random subset of the data rather than the whole big data matrix. In the provided analysis, it is shown that the sufficient number of randomly sampled columns/rows scales linearly with the rank and the coherency parameter of the low rank component.

Publication Date

2-26-2016

Publication Title

Conference Record - Asilomar Conference on Signals, Systems and Computers

Volume

2016-February

Number of Pages

1796-1800

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ACSSC.2015.7421461

Socpus ID

84969856691 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84969856691

This document is currently not available here.

Share

COinS