This paper considers the use of robust principal component analysis (RPCA) in a CUR decomposition framework and applications thereof. Our main algorithms produce a robust version of column-row fact...

Robust principal component analysis (RPCA) is a widely used tool for dimension reduction. In this work, we propose a novel non-convex algorithm, coined Iterated Robust CUR (IRCUR), for solving RPCA problems, which dramatically improves the computational efficiency in comparison with the existing algorithms. IRCUR achieves this acceleration by employing CUR decomposition when updating the low rank component, which allows us to obtain an accurate low rank approximation via only three small submatrices. Consequently, IRCUR is able to process only the small submatrices and avoid the expensive computing on full matrix through the entire algorithm. Numerical experiments establish the computational advantage of IRCUR over the state-of-art algorithms on both synthetic and real-world datasets.

The CUR decomposition is a factorization of a low-rank matrix obtained by selecting certain column and row submatrices of it. We perform a thorough investigation of what happens to such decompositi...

We analyze the problem of reconstruction of a bandlimited function f from the space–time samples of its states $$f_t=\phi _t*f$$f t = ϕ t ∗ f resulting from the convolution with a kernel $$\phi _t$$ϕ t . It is well-known that, in natural phenomena, uniform space–time samples of f are not sufficient to reconstruct f in a stable way. To enable stable reconstruction, a space–time sampling with periodic nonuniformly spaced samples must be used as was shown by Lu and Vetterli. We show that the stability of reconstruction, as measured by a condition number, controls the maximal gap between the spacial samples. We provide a quantitative statement of this result. In addition, instead of irregular space–time samples, we show that uniform dynamical samples at sub-Nyquist spatial rate allow one to stably reconstruct the function $$\widehat{f}$$f ^ away from certain, explicitly described blind spots. We also consider several classes of finite dimensional subsets of bandlimited functions in which the stable reconstruction is possible, even inside the blind spots. We obtain quantitative estimates for it using Remez-Turán type inequalities. En route, we obtain Remez-Turán inequality for prolate spheroidal wave functions. To illustrate our results, we present some numerics and explicit estimates for the heat flow problem.

While uniform sampling has been widely studied in the matrix completion literature, CUR sampling approximates a low-rank matrix via row and column samples. Unfortunately, both sampling models lack flexibility for various circumstances in real-world applications. In this work, we propose a novel and easy-to-implement sampling strategy, coined Cross-Concentrated Sampling (CCS). By bridging uniform sampling and CUR sampling, CCS provides extra flexibility that can potentially save sampling costs in applications. In addition, we also provide a sufficient condition for CCS-based matrix completion. Moreover, we propose a highly efficient non-convex algorithm, termed Iterative CUR Completion (ICURC), for the proposed CCS model. Numerical experiments verify the empirical advantages of CCS and ICURC against uniform sampling and its baseline algorithms, on both synthetic and real-world datasets.

This article studies how to form CUR decompositions of low-rank matrices via primarily random sampling, though deterministic methods due to previous works are illustrated as well. The primary problem is to determine when a column submatrix of a rank $ k $ matrix also has rank $ k $. For random column sampling schemes, there is typically a tradeoff between the number of columns needed to be chosen and the complexity of determining the sampling probabilities. We discuss several sampling methods and their complexities as well as stability of the method under perturbations of both the probabilities and the underlying matrix. As an application, we give a high probability guarantee of the exact solution of the Subspace Clustering Problem via CUR decompositions when columns are sampled according to their Euclidean lengths.