Exact Recoverability of Robust PCA via Outlier Pursuit with Tight Recovery Bounds
Authors: Hongyang Zhang, Zhouchen Lin, Chao Zhang, Edward Chang
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments This section aims at verifying the validity of our theories by numerical experiments. We solve Outlier Pursuit by the alternating direction method (Lin, Liu, and Su 2011), which is probably the most efficient algorithm for solving nuclear norm minimization problems. Details can be found in the supplementary material. |
| Researcher Affiliation | Collaboration | Key Lab. of Machine Perception (MOE), School of EECS, Peking University, China HTC Research, Taiwan |
| Pseudocode | No | The paper describes algorithms (e.g., 'alternating direction method') but does not provide formal pseudocode blocks or algorithm listings. |
| Open Source Code | No | The paper does not provide any statement or link regarding the public availability of source code for the described methodology. |
| Open Datasets | Yes | To test the performance of Outlier Pursuit (2) on the real data, we conduct an experiment on the Hopkins 155 database1. 1http://www.vision.jhu.edu/data/hopkins155 |
| Dataset Splits | No | The paper describes data generation and use of the Hopkins 155 database but does not provide specific train/validation/test splits for reproducibility. |
| Hardware Specification | No | The paper does not specify any hardware details (e.g., CPU, GPU models, or memory) used for the experiments. |
| Software Dependencies | No | The paper mentions using 'the alternating direction method' but does not specify any software names with version numbers (e.g., programming languages, libraries, or frameworks) used for implementation. |
| Experiment Setup | Yes | We construct L0 = XY T as a product of n r i.i.d. N(0, 1) matrices. The nonzero columns of S0 are uniformly selected, whose entries follow i.i.d. N(0, 1). Finally, we construct our observation matrix M = L0 + S0. We solve the Outlier Pursuit (2) to obtain an optimal solution (L , S ) and then compare with (L0, S0). The distance between the column spaces are measured by ||PU PU0||F and the distance between the column supports is measured by the Hamming distance. We run the experiment by 10 times and report the average results. Table 2 shows that our choice of λ can make Outlier Pursuit exactly recover the column space of L0 and the column support of S0. To verify that the success of Outlier Pursuit (2) is robust to various noise magnitudes, we test the cases where the entries of S0 follow i.i.d. N(0, 1/n), N(0, 1), and N(0, 100), respectively. We specifically adopt n = 1, 500, while all the other settings are the same as the experiment above. Table 3 shows that Outlier Pursuit (2) could exactly recover the ground truth subspace and correctly identify the noise index, no matter what magnitude the noises are. |