Exact recoverability of Robust PCA via outlier Pursuit with tight recovery bounds | |
Zhang, Hongyang ; Lin, Zhouchen ; Zhang, Chao ; Chang, Edward Y. | |
2015 | |
英文摘要 | Subspace recovery from noisy or even corrupted data is critical for various applications in machine learning and data analysis. To detect outliers, Robust PCA (R-PCA) via Outlier Pursuit was proposed and had found many successful applications. However, the current theoretical analysis on Outlier Pursuit only shows that it succeeds when the sparsity of the corruption matrix is of O(n/r), where n is the number of the samples and r is the rank of the intrinsic matrix which may be comparable to n. Moreover, the regularization parameter is suggested as 3/(7/7n), where γ is a parameter that is not known a priori. In this paper, with incoherence condition and proposed ambiguity condition we prove that Outlier Pursuit succeeds when the rank of the intrinsic matrix is of O(n/logn) and the sparsity of the corruption matrix is of O(n). We further show that the orders of both bounds are tight. Thus R-PCA via Outlier Pursuit is able to recover intrinsic matrix of higher rank and identify much denser corruptions than what the existing results could predict. Moreover. we suggest that the regularization parameter be chosen as l/v'logn, which is definite. Our analysis waives the necessity of tuning the regularization parameter and also significantly extends the working range of the Outlier Pursuit. Experiments on synthetic and real data verify our theories. ? 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; EI; 3143-3149; 4 |
语种 | 英语 |
出处 | 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015 |
内容类型 | 其他 |
源URL | [http://ir.pku.edu.cn/handle/20.500.11897/436805] |
专题 | 信息科学技术学院 |
推荐引用方式 GB/T 7714 | Zhang, Hongyang,Lin, Zhouchen,Zhang, Chao,et al. Exact recoverability of Robust PCA via outlier Pursuit with tight recovery bounds. 2015-01-01. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论