Timezone: »
Spotlight
Non-convex Robust PCA
Praneeth Netrapalli · Niranjan Uma Naresh · Sujay Sanghavi · Animashree Anandkumar · Prateek Jain
Wed Dec 10 07:10 AM -- 07:30 AM (PST) @ Level 2, room 210
We propose a new provable method for robust PCA, where the task is to recover a low-rank matrix, which is corrupted with sparse perturbations. Our method consists of simple alternating projections onto the set of low rank and sparse matrices with intermediate de-noising steps. We prove correct recovery of the low rank and sparse components under tight recovery conditions, which match those for the state-of-art convex relaxation techniques. Our method is extremely simple to implement and has low computational complexity. For a $m \times n$ input matrix (say m \geq n), our method has O(r^2 mn\log(1/\epsilon)) running time, where $r$ is the rank of the low-rank component and $\epsilon$ is the accuracy. In contrast, the convex relaxation methods have a running time O(mn^2/\epsilon), which is not scalable to large problem instances. Our running time nearly matches that of the usual PCA (i.e. non robust), which is O(rmn\log (1/\epsilon)). Thus, we achieve ``best of both the worlds'', viz low computational complexity and provable recovery for robust PCA. Our analysis represents one of the few instances of global convergence guarantees for non-convex methods.
Author Information
Praneeth Netrapalli (Google Research)
Niranjan Uma Naresh (UC Irvine)
Sujay Sanghavi (UT-Austin)
Animashree Anandkumar (NVIDIA / Caltech)
Prateek Jain (Microsoft Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2014 Poster: Non-convex Robust PCA »
Thu. Dec 11th 12:00 -- 04:59 AM Room Level 2, room 210D
More from the Same Authors
-
2022 : Differentially Private Federated Learning with Normalized Updates »
Rudrajit Das · Abolfazl Hashemi · Sujay Sanghavi · Inderjit Dhillon -
2022 : MET: Masked Encoding for Tabular Data »
Kushal Majmundar · Sachin Goyal · Praneeth Netrapalli · Prateek Jain -
2022 : Learning an Invertible Output Mapping Can Mitigate Simplicity Bias in Neural Networks »
Sravanti Addepalli · Anshul Nasery · Venkatesh Babu R · Praneeth Netrapalli · Prateek Jain -
2023 Poster: Simplicity Bias in 1-Hidden Layer Neural Networks »
Depen Morwani · Jatin Batra · Prateek Jain · Praneeth Netrapalli -
2023 Poster: Logarithmic Bayes Regret Bounds »
Alexia Atsidakou · Branislav Kveton · Sumeet Katariya · Constantine Caramanis · Sujay Sanghavi -
2023 Poster: Geometry-Informed Neural Operator for Large-Scale 3D PDEs »
Zongyi Li · Nikola Kovachki · Chris Choy · Boyi Li · Jean Kossaifi · Shourya Otta · Mohammad Amin Nabian · Maximilian Stadler · Christian Hundt · Kamyar Azizzadenesheli · Animashree Anandkumar -
2023 Workshop: Workshop on Advancing Neural Network Training (WANT): Computational Efficiency, Scalability, and Resource Optimization »
Julia Gusak · Jean Kossaifi · Alena Shilova · Cristiana Bentes · Animashree Anandkumar · Olivier Beaumont -
2023 Workshop: The Symbiosis of Deep Learning and Differential Equations -- III »
Luca Celotti · Martin Magill · Ermal Rrapaj · Winnie Xu · Qiyao Wei · Archis Joglekar · Michael Poli · Animashree Anandkumar -
2023 Workshop: New Frontiers of AI for Drug Discovery and Development »
Animashree Anandkumar · Ilija Bogunovic · Ti-chiun Chang · Quanquan Gu · Jure Leskovec · Michelle Li · Chong Liu · NataĊĦa Tagasovska · Wei Wang -
2022 Poster: Minimax Regret for Cascading Bandits »
Daniel Vial · Sujay Sanghavi · Sanjay Shakkottai · R. Srikant -
2022 Poster: Toward Understanding Privileged Features Distillation in Learning-to-Rank »
Shuo Yang · Sujay Sanghavi · Holakou Rahmanian · Jan Bakus · Vishwanathan S. V. N. -
2022 Poster: Reproducibility in Optimization: Theoretical Framework and Limits »
Kwangjun Ahn · Prateek Jain · Ziwei Ji · Satyen Kale · Praneeth Netrapalli · Gil I Shamir -
2021 Social: ML in India: A Billion Opportunities »
Praneeth Netrapalli · Srujana Merugu -
2021 Poster: Nearly Horizon-Free Offline Reinforcement Learning »
Tongzheng Ren · Jialian Li · Bo Dai · Simon Du · Sujay Sanghavi -
2019 Poster: Interaction Hard Thresholding: Consistent Sparse Quadratic Regression in Sub-quadratic Time and Space »
Shuo Yang · Yanyao Shen · Sujay Sanghavi -
2019 Poster: Provable Non-linear Inductive Matrix Completion »
Kai Zhong · Zhao Song · Prateek Jain · Inderjit Dhillon -
2019 Poster: Efficient Algorithms for Smooth Minimax Optimization »
Kiran Thekumparampil · Prateek Jain · Praneeth Netrapalli · Sewoong Oh -
2019 Poster: Shallow RNN: Accurate Time-series Classification on Resource Constrained Devices »
Don Dennis · Durmus Alp Emre Acar · Vikram Mandikal · Vinu Sankar Sadasivan · Venkatesh Saligrama · Harsha Vardhan Simhadri · Prateek Jain -
2019 Poster: Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models »
Shanshan Wu · Sujay Sanghavi · Alex Dimakis -
2019 Spotlight: Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models »
Shanshan Wu · Sujay Sanghavi · Alex Dimakis -
2019 Poster: Iterative Least Trimmed Squares for Mixed Linear Regression »
Yanyao Shen · Sujay Sanghavi -
2019 Poster: Blocking Bandits »
Soumya Basu · Rajat Sen · Sujay Sanghavi · Sanjay Shakkottai -
2019 Poster: Learning Distributions Generated by One-Layer ReLU Networks »
Shanshan Wu · Alex Dimakis · Sujay Sanghavi -
2018 : Poster Session »
Sujay Sanghavi · Vatsal Shah · Yanyao Shen · Tianchen Zhao · Yuandong Tian · Tomer Galanti · Mufan Li · Gilad Cohen · Daniel Rothchild · Aristide Baratin · Devansh Arpit · Vagelis Papalexakis · Michael Perlmutter · Ashok Vardhan Makkuva · Pim de Haan · Yingyan Lin · Wanmo Kang · Cheolhyoung Lee · Hao Shen · Sho Yaida · Dan Roberts · Nadav Cohen · Philippe Casgrain · Dejiao Zhang · Tengyu Ma · Avinash Ravichandran · Julian Emilio Salazar · Bo Li · Davis Liang · Christopher Wong · Glen Bigan Mbeng · Animesh Garg -
2018 Workshop: 2nd Workshop on Machine Learning on the Phone and other Consumer Devices (MLPCD 2) »
Sujith Ravi · Wei Chai · Yangqing Jia · Hrishikesh Aradhye · Prateek Jain -
2018 Poster: Support Recovery for Orthogonal Matching Pursuit: Upper and Lower bounds »
Raghav Somani · Chirag Gupta · Prateek Jain · Praneeth Netrapalli -
2018 Spotlight: Support Recovery for Orthogonal Matching Pursuit: Upper and Lower bounds »
Raghav Somani · Chirag Gupta · Prateek Jain · Praneeth Netrapalli -
2018 Poster: FastGRNN: A Fast, Accurate, Stable and Tiny Kilobyte Sized Gated Recurrent Neural Network »
Aditya Kusupati · Manish Singh · Kush Bhatia · Ashish Kumar · Prateek Jain · Manik Varma -
2018 Poster: Multiple Instance Learning for Efficient Sequential Data Classification on Resource-constrained Devices »
Don Dennis · Chirag Pabbaraju · Harsha Vardhan Simhadri · Prateek Jain -
2017 Poster: Learning Mixture of Gaussians with Streaming Data »
Aditi Raghunathan · Prateek Jain · Ravishankar Krishnawamy -
2017 Poster: Consistent Robust Regression »
Kush Bhatia · Prateek Jain · Parameswaran Kamalaruban · Purushottam Kar -
2016 Workshop: Learning in High Dimensions with Structure »
Nikhil Rao · Prateek Jain · Hsiang-Fu Yu · Ming Yuan · Francis Bach -
2016 Poster: Single Pass PCA of Matrix Products »
Shanshan Wu · Srinadh Bhojanapalli · Sujay Sanghavi · Alex Dimakis -
2016 Poster: Regret Bounds for Non-decomposable Metrics with Missing Labels »
Nagarajan Natarajan · Prateek Jain -
2016 Poster: Structured Sparse Regression via Greedy Hard Thresholding »
Prateek Jain · Nikhil Rao · Inderjit Dhillon -
2016 Poster: Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent »
Chi Jin · Sham Kakade · Praneeth Netrapalli -
2016 Poster: Selective inference for group-sparse linear models »
Fan Yang · Rina Barber · Prateek Jain · John Lafferty -
2016 Poster: Mixed Linear Regression with Multiple Components »
Kai Zhong · Prateek Jain · Inderjit Dhillon -
2016 Poster: Normalized Spectral Map Synchronization »
Yanyao Shen · Qixing Huang · Nati Srebro · Sujay Sanghavi -
2015 Poster: Robust Regression via Hard Thresholding »
Kush Bhatia · Prateek Jain · Purushottam Kar -
2015 Poster: Sparse Local Embeddings for Extreme Multi-label Classification »
Kush Bhatia · Himanshu Jain · Purushottam Kar · Manik Varma · Prateek Jain -
2015 Poster: Predtron: A Family of Online Algorithms for General Prediction Problems »
Prateek Jain · Nagarajan Natarajan · Ambuj Tewari -
2015 Poster: Convergence Rates of Active Learning for Maximum Likelihood Estimation »
Kamalika Chaudhuri · Sham Kakade · Praneeth Netrapalli · Sujay Sanghavi -
2015 Poster: Alternating Minimization for Regression Problems with Vector-valued Outputs »
Prateek Jain · Ambuj Tewari -
2014 Poster: Provable Tensor Factorization with Missing Data »
Prateek Jain · Sewoong Oh -
2014 Poster: Provable Submodular Minimization using Wolfe's Algorithm »
Deeparnab Chakrabarty · Prateek Jain · Pravesh Kothari -
2014 Poster: Online and Stochastic Gradient Methods for Non-decomposable Loss Functions »
Purushottam Kar · Harikrishna Narasimhan · Prateek Jain -
2014 Oral: Provable Submodular Minimization using Wolfe's Algorithm »
Deeparnab Chakrabarty · Prateek Jain · Pravesh Kothari -
2014 Poster: Greedy Subspace Clustering »
Dohyung Park · Constantine Caramanis · Sujay Sanghavi -
2014 Poster: On Iterative Hard Thresholding Methods for High-dimensional M-Estimation »
Prateek Jain · Ambuj Tewari · Purushottam Kar -
2013 Poster: Phase Retrieval using Alternating Minimization »
Praneeth Netrapalli · Prateek Jain · Sujay Sanghavi -
2013 Poster: Memory Limited, Streaming PCA »
Ioannis Mitliagkas · Constantine Caramanis · Prateek Jain -
2012 Poster: Multilabel Classification using Bayesian Compressed Sensing »
Ashish Kapoor · Raajay Viswanathan · Prateek Jain -
2012 Poster: Clustering Sparse Graphs »
Yudong Chen · Sujay Sanghavi · Huan Xu -
2012 Poster: Supervised Learning with Similarity Functions »
Purushottam Kar · Prateek Jain -
2011 Poster: High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions »
Animashree Anandkumar · Vincent Tan · Alan S Willsky -
2011 Oral: High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions »
Animashree Anandkumar · Vincent Tan · Alan S Willsky -
2011 Poster: Orthogonal Matching Pursuit with Replacement »
Prateek Jain · Ambuj Tewari · Inderjit Dhillon -
2011 Poster: Similarity-based Learning via Data Driven Embeddings »
Purushottam Kar · Prateek Jain -
2010 Workshop: Robust Statistical Learning »
Pradeep Ravikumar · Constantine Caramanis · Sujay Sanghavi -
2010 Spotlight: Guaranteed Rank Minimization via Singular Value Projection »
Prateek Jain · Raghu Meka · Inderjit Dhillon -
2010 Poster: Guaranteed Rank Minimization via Singular Value Projection »
Prateek Jain · Raghu Meka · Inderjit Dhillon -
2010 Spotlight: Inductive Regularized Learning of Kernel Functions »
Prateek Jain · Brian Kulis · Inderjit Dhillon -
2010 Oral: A Dirty Model for Multi-task Learning »
Ali Jalali · Pradeep Ravikumar · Sujay Sanghavi · Chao Ruan -
2010 Poster: Inductive Regularized Learning of Kernel Functions »
Prateek Jain · Brian Kulis · Inderjit Dhillon -
2010 Poster: Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning »
Prateek Jain · Sudheendra Vijayanarasimhan · Kristen Grauman -
2010 Poster: Robust PCA via Outlier Pursuit »
Huan Xu · Constantine Caramanis · Sujay Sanghavi -
2010 Poster: A Dirty Model for Multi-task Learning »
Ali Jalali · Pradeep Ravikumar · Sujay Sanghavi · Chao Ruan -
2009 Poster: Matrix Completion from Power-Law Distributed Samples »
Raghu Meka · Prateek Jain · Inderjit Dhillon -
2008 Poster: Online Metric Learning and Fast Similarity Search »
Prateek Jain · Brian Kulis · Inderjit Dhillon · Kristen Grauman -
2008 Oral: Online Metric Learning and Fast Similarity Search »
Prateek Jain · Brian Kulis · Inderjit Dhillon · Kristen Grauman -
2007 Spotlight: Message Passing for Max-weight Independent Set »
Sujay Sanghavi · Devavrat Shah · Alan S Willsky -
2007 Poster: Message Passing for Max-weight Independent Set »
Sujay Sanghavi · Devavrat Shah · Alan S Willsky -
2007 Poster: Linear programming analysis of loopy belief propagation for weighted matching »
Sujay Sanghavi · Dmitry Malioutov · Alan S Willsky