NDLI: Fast algorithms for recovering a corrupted low-rank matrix

Content Provider	IEEE Xplore Digital Library
Author	Ganesh, A. Zhouchen Lin Wright, J. Leqin Wu Minming Chen Yi Ma
Copyright Year	2009
Description	Author affiliation: Microsoft Research Asia, China (Zhouchen Lin; Wright, J.) \|\| ECE Department, University of Illinois, Urbana-Champaign, USA (Ganesh, A.; Yi Ma) \|\| Institute of Computing Technology, Chinese Academy of Sciences, China (Leqin Wu) \|\| Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, China (Minming Chen)
Abstract	This paper studies algorithms for solving the problem of recovering a low-rank matrix with a fraction of its entries arbitrarily corrupted. This problem can be viewed as a robust version of classical PCA, and arises in a number of application domains, including image processing, web data ranking, and bioinformatic data analysis. It was recently shown that under surprisingly broad conditions, it can be exactly solved via a convex programming surrogate that combines nuclear norm minimization and $ℓ^{1}-norm$ minimization. This paper develops and compares two complementary approaches for solving this convex program. The first is an accelerated proximal gradient algorithm directly applied to the primal; while the second is a gradient algorithm applied to the dual problem. Both are several orders of magnitude faster than the previous state-of-the-art algorithm for this problem, which was based on iterative thresholding. Simulations demonstrate the performance improvement that can be obtained via these two algorithms, and clarify their relative merits.
Starting Page	213
Ending Page	216
File Size	289773
Page Count	4
File Format	PDF
ISBN	9781424451791
DOI	10.1109/CAMSAP.2009.5413299
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-12-13
Publisher Place	Aruba
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computers Data analysis Conferences Asia Iterative algorithms Robustness Mathematics Sparse matrices Principal component analysis Convergence
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in