CUR from a Sparse Optimization Viewpoint

Abstract

The CUR decomposition provides an approximation of a matrix $X$ that has low reconstruction error and that is sparse in the sense that the resulting approximation lies in the span of only a few columns of $X$. In this regard, it appears to be similar to many sparse PCA methods. However, CUR takes a randomized algorithmic approach, whereas most sparse PCA methods are framed as convex optimization problems. In this paper, we try to understand CUR from a sparse optimization viewpoint. We show that CUR is implicitly optimizing a sparse regression objective and, furthermore, cannot be directly cast as a sparse PCA method. We also observe that the sparsity attained by CUR possesses an interesting structure, which leads us to formulate a sparse PCA method that achieves a CUR-like sparsity.

9 pages; in NIPS 2010

References in corpus (1)

• Structured Sparse Principal Component Analysis

Cited by in corpus (9)

• Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
• Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization
• Network Flow Algorithms for Structured Sparsity
• Convex and Network Flow Optimization for Structured Sparsity
• Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
• CUR Algorithm for Partially Observed Matrices
• The Singular Value Decomposition, Applications and Beyond
• CUR Decompositions, Approximations, and Perturbations
• Perspectives on CUR Decompositions