Randomized subspace learning approach for high dimensional low rank plus sparse matrix decomposition

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.