• PDF
• Cite
• Share
Article Contents  Article Contents

# Stability of sampling for CUR decompositions

• * Corresponding author: Longxiu Huang
The first author is partially supported by the National Science Foundation TRIPODS program, grant number NSF CCF–1740858. The second author is partially supported by NSF CAREER DMS 1348721 and NSF BIGDATA 1740325
• 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.

Mathematics Subject Classification: Primary: 15A23, 65F30; Secondary: 68W20.

 Citation: • • Table 1.  Table summarizing sampling complexities for different algorithms

 Sampling # Rows # Cols Success Prob Complexity Ref $p_i^\text{unif}, q_i^\text{unif}$ $\frac{r}{ \varepsilon^4\delta}\log(\frac{r}{ \varepsilon^4\delta})$ $\frac{r}{ \varepsilon^4\delta}\log(\frac{r}{ \varepsilon^4\delta})$ $(1-2e^{-c\gamma^2/\delta})^2$ $O(1)$ Cor 5.2 $p_i^\text{col}, q_i^\text{col}$ $\frac{r}{ \varepsilon^4\delta}\log(\frac{r}{ \varepsilon^4\delta})$ $\frac{r}{ \varepsilon^4\delta}\log(\frac{r}{ \varepsilon^4\delta})$ $(1-2e^{-c/\delta})^2$ $O(mn)$ Thm 4.1 $p_i^\text{col}, q_i^\text{col}$ $r\kappa(A)^2(\log(k)+\frac{1}{\delta})$ $r\kappa(A)^2(\log(k)+\frac{1}{\delta})$ $(1-2e^{-c/\delta})^2$ $O(mn)$ Cor 6.4 $p_i^{\text{lev}, k}, q_i^{\text{lev}, k}$ $\frac{k^2}{ \varepsilon^2\delta}$ $\frac{k^2}{ \varepsilon^2\delta}$ $1-e^{-1/\delta}$ $O(\text{SVD}(A, k))$  $p_i^{\text{lev}, k}, q_i^{\text{lev}, k}$ $k\log(k)+\frac{k}{\delta}$ $k\log(k)+\frac{k}{\delta}$ $(1-2e^{-1/\delta})^2$ $O(\text{SVD}(A, k))$  DEIM-CUR $k$ $k$ 1 $O(\text{SVD}(A, k) + k^4)$  RRQR-CUR $k$ $k$ 1 $O(\text{RRQR}(A))$ 
• Tables(1)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint