1 Introduction
1.1 Main contributions
1.2 Connections and differences with previous work
1.2.1 Organization
2 Background
2.1 Reformulating RPCA with SDP
2.2 Outline of our algorithm
2.3 Graph representation of a partially observed matrix Z
2.4 Heuristics for finding cliques
3 Decomposing the submatrix \(\bar{Z}\) using PALM
4 Facial reduction, bicliques and exposing vectors
4.1 Preliminaries on faces
4.2 Exposing vector
4.3 Reducing problem size using FR
4.4 Further reducing the size of the problem
4.5 Detecting the target rank
Specifications | True \(r=\) | Percent of estimated ranks | ||||||
---|---|---|---|---|---|---|---|---|
m | n | \(D_S\) | \(r-1\) | r | \(r+1\) | \(r+2\) | \(r+3\) | |
10 | 10 | 0.01 | 2 | 0 | 100 | 0 | 0 | 0 |
15 | 15 | 0.01 | 2 | 0 | 96 | 4 | 0 | 0 |
20 | 20 | 0.01 | 2 | 0 | 85 | 12 | 3 | 0 |
10 | 10 | 0.02 | 3 | 0 | 90 | 9 | 1 | 0 |
15 | 15 | 0.02 | 3 | 0 | 71 | 15 | 7 | 7 |
20 | 20 | 0.02 | 3 | 0 | 61 | 13 | 12 | 14 |
10 | 10 | 0.03 | 4 | 0 | 56 | 18 | 17 | 9 |
15 | 15 | 0.03 | 4 | 0 | 55 | 20 | 11 | 14 |
5 Growing bicliques by submatrix completion
6 Numerical experiments
6.1 Noiseless case
Specifications | Succ | CPU | \(\hat{r}\) | \(K_{min}\) | \(K_{max}\) | \(\mu\) | ||
---|---|---|---|---|---|---|---|---|
m | n | \(\delta\) | ||||||
800 | 800 | 0.18 | 14 | 11.55 | 2 | 10 | 50 | 0.88 |
1000 | 1000 | 0.18 | 19 | 14.55 | 2 | 10 | 50 | 0.79 |
1200 | 1200 | 0.18 | 18 | 23.52 | 2 | 10 | 50 | 0.29 |
1500 | 1500 | 0.18 | 17 | 27.77 | 2 | 10 | 50 | 0.26 |
1800 | 1800 | 0.18 | 17 | 33.43 | 2 | 10 | 50 | 0.12 |
2100 | 2100 | 0.18 | 19 | 37.84 | 2 | 10 | 50 | 0.11 |
3000 | 3000 | 0.18 | 17 | 54.61 | 2 | 10 | 50 | 0.09 |
5000 | 5000 | 0.18 | 16 | 106.87 | 2 | 10 | 50 | 0.07 |
Specifications | Succ | CPU | \(\hat{r}\) | \(K_{min}\) | \(K_{max}\) | \(\mu\) | ||
---|---|---|---|---|---|---|---|---|
m | n | \(\delta\) | ||||||
800 | 800 | 0.26 | 18 | 17.74 | 3 | 10 | 60 | 0.12 |
1000 | 1000 | 0.26 | 14 | 21.20 | 3 | 10 | 60 | 0.11 |
1500 | 1500 | 0.26 | 14 | 30.32 | 3 | 10 | 60 | 0.09 |
2000 | 2000 | 0.26 | 18 | 41.83 | 3 | 12 | 60 | 0.07 |
2500 | 2500 | 0.26 | 18 | 48.74 | 3 | 12 | 60 | 0.07 |
3000 | 3000 | 0.26 | 19 | 67.17 | 3 | 12 | 60 | 0.06 |
4000 | 4000 | 0.26 | 16 | 97.61 | 3 | 12 | 60 | 0.05 |
5000 | 5000 | 0.26 | 16 | 119.99 | 3 | 12 | 60 | 0.05 |
Specifications | Succ FR | Succ FALM | CPU FR | CPU FALM | |||
---|---|---|---|---|---|---|---|
m | n | \(\delta\) | r | ||||
500 | 500 | 0.33 | 4 | 18 | 0 | 15.88 | 11.07 |
500 | 500 | 0.36 | 4 | 19 | 0 | 9.33 | 11.11 |
500 | 500 | 0.45 | 4 | 20 | 8 | 5.00 | 10.92 |
500 | 500 | 0.5 | 4 | 20 | 18 | 5.38 | 11.66 |
600 | 600 | 0.22 | 3 | 18 | 0 | 25.62 | 15.03 |
1000 | 1000 | 0.22 | 3 | 16 | 0 | 18.16 | 72.22 |
1000 | 1000 | 0.33 | 3 | 17 | 0 | 23.81 | 72.61 |
1000 | 1000 | 0.45 | 3 | 20 | 20 | 11.73 | 76.22 |
1000 | 1000 | 0.36 | 5 | 20 | 1 | 29.36 | 75.49 |
1000 | 1000 | 0.39 | 5 | 20 | 14 | 27.88 | 77.53 |
2000 | 2000 | 0.28 | 5 | 14 | 6 | 67.76 | 615.62 |
2000 | 2000 | 0.33 | 5 | 20 | 18 | 56.74 | 651.81 |
2000 | 2000 | 0.26 | 3 | 18 | 0 | 41.83 | 662.70 |
2000 | 2000 | 0.36 | 3 | 20 | 20 | 36.74 | 673.05 |
2100 | 2100 | 0.18 | 2 | 19 | 0 | 37.84 | 728.17 |
3000 | 3000 | 0.18 | 2 | 17 | 0 | 54.61 | 2216.66 |
Specifications | Succ FR | Succ FGD | CPU FR | CPU FGD | |||
---|---|---|---|---|---|---|---|
m | n | \(\delta\) | r | ||||
800 | 800 | 0.18 | 2 | 18 | 0 | 13.85 | 0.692172 |
1000 | 1000 | 0.18 | 2 | 20 | 0 | 18.53 | 1.293400 |
1200 | 1200 | 0.18 | 2 | 20 | 0 | 36.27 | 1.878267 |
1500 | 1500 | 0.18 | 2 | 16 | 0 | 41.98 | 2.596376 |
1800 | 1800 | 0.18 | 2 | 18 | 0 | 53.83 | 3.587537 |
2100 | 2100 | 0.18 | 2 | 18 | 0 | 63.12 | 5.182643 |
3000 | 3000 | 0.18 | 2 | 16 | 0 | 101.09 | 9.338740 |
Specifications | Succ FR | Succ FGD | CPU FR | CPU FGD | |||
---|---|---|---|---|---|---|---|
m | n | \(\delta\) | r | ||||
800 | 800 | 0.18 | 2 | 20 | 0 | 12.14 | 0.761310 |
1000 | 1000 | 0.18 | 2 | 20 | 0 | 15.54 | 1.196388 |
1200 | 1200 | 0.18 | 2 | 20 | 10 | 30.32 | 1.729541 |
1500 | 1500 | 0.18 | 2 | 20 | 18 | 32.78 | 2.624523 |
1800 | 1800 | 0.18 | 2 | 20 | 20 | 39.92 | 3.770775 |
2100 | 2100 | 0.18 | 2 | 20 | 20 | 48.48 | 4.905493 |
3000 | 3000 | 0.18 | 2 | 12 | 20 | 51.20 | 10.816730 |
6.2 Noisy case
Specifications | CPU FR | CPU FALM | Rank | Res (FR) | Res (FALM) | ||
---|---|---|---|---|---|---|---|
m | n | Mean(p) | |||||
600 | 600 | 0.33 | 7.19 | 17.55 | 2 | 1.730694e−04 | 1.478195e−03 |
800 | 800 | 0.33 | 10.56 | 38.00 | 2 | 1.189773e−04 | 1.005278e−03 |
1000 | 1000 | 0.26 | 14.30 | 78.66 | 2 | 1.123756e−04 | 2.154113e−03 |
1500 | 1500 | 0.26 | 21.28 | 280.05 | 2 | 1.853607e−04 | 9.815458e−04 |
2000 | 2000 | 0.26 | 50.63 | 687.00 | 2 | 1.120183e−04 | 1.388883e−04 |
Specifications | CPU FR | CPU FALM | Rank | Res (FR) | Res (FALM) | ||
---|---|---|---|---|---|---|---|
m | n | Mean(p) | |||||
600 | 600 | 0.33 | 9.44 | 17.49 | 3 | 6.600662e−05 | 1.837060e−03 |
600 | 600 | 0.36 | 6.53 | 18.25 | 3 | 1.808533e−05 | 1.156141e−03 |
800 | 800 | 0.33 | 9.70 | 39.08 | 3 | 2.187891e−05 | 1.033397e−03 |
800 | 800 | 0.36 | 8.65 | 38.29 | 3 | 1.240057e−05 | 8.217820e−04 |
1000 | 1000 | 0.33 | 11.98 | 80.09 | 3 | 1.523253e−05 | 5.252964e−04 |
1000 | 1000 | 0.36 | 11.38 | 79.56 | 3 | 1.125439e−05 | 3.015739e−04 |
1500 | 1500 | 0.33 | 19.89 | 284.93 | 3 | 1.220386e−05 | 7.854144e−05 |
1500 | 1500 | 0.36 | 23.08 | 302.34 | 3 | 1.022679e−05 | 5.251847e−05 |
2000 | 2000 | 0.33 | 43.87 | 728.43 | 3 | 1.088412e−05 | 2.258433e−05 |