A Subspace Learning Approach For High Dimensional Matrix Decomposition With Efficient Column/Row Sampling

Abstract

This paper presents a new randomized approach to high-dimensional low rank (LR) plus sparse matrix decomposition. For a data matrix D ϵ ℝN1×N2, the complexity of conventional decomposition methods is O(N1N2r), which limits their usefulness in big data settings (r is the rank of the LR component). In addition, the existing randomized approaches rely for the most part on uniform random sampling, which may be inefficient for many real world data matrices. The proposed subspace learning-based approach recovers the LR component using only a small subset of the columns/rows of data and reduces complexity to O(max(N1,N2)r2). Even when the columns/rows are sampled uniformly at random, the sufficient number of sampled columns/rows is shown to be roughly O(rμ), where μ is the coherency parameter of the LR component. In addition, efficient sampling algorithms are proposed to address the problem of column/row sampling from structured data.

Publication Date

1-1-2016

Publication Title

33rd International Conference on Machine Learning, ICML 2016

Volume

3

Number of Pages

1846-1854

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

84999040456 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS