Nearly Optimal Robust Subspace Tracking

Praneeth Narayanamurthy, Namrata Vaswani
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3701-3709, 2018.

Abstract

Robust subspace tracking (RST) can be simply understood as a dynamic (time-varying) extension of robust PCA. More precisely, it is the problem of tracking data lying in a fixed or slowly-changing low-dimensional subspace while being robust to sparse outliers. This work develops a recursive projected compressive sensing algorithm called “Nearly Optimal RST (NORST)”, and obtains one of the first guarantees for it. We show that NORST provably solves RST under weakened standard RPCA assumptions, slow subspace change, and a lower bound on (most) outlier magnitudes. Our guarantee shows that (i) NORST is online (after initialization) and enjoys near-optimal values of tracking delay, lower bound on required delay between subspace change times, and of memory complexity; and (ii) it has a significantly improved worst-case outlier tolerance compared with all previous robust PCA or RST methods without requiring any model on how the outlier support is generated.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-narayanamurthy18a, title = {Nearly Optimal Robust Subspace Tracking}, author = {Narayanamurthy, Praneeth and Vaswani, Namrata}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3701--3709}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/narayanamurthy18a/narayanamurthy18a.pdf}, url = {https://proceedings.mlr.press/v80/narayanamurthy18a.html}, abstract = {Robust subspace tracking (RST) can be simply understood as a dynamic (time-varying) extension of robust PCA. More precisely, it is the problem of tracking data lying in a fixed or slowly-changing low-dimensional subspace while being robust to sparse outliers. This work develops a recursive projected compressive sensing algorithm called “Nearly Optimal RST (NORST)”, and obtains one of the first guarantees for it. We show that NORST provably solves RST under weakened standard RPCA assumptions, slow subspace change, and a lower bound on (most) outlier magnitudes. Our guarantee shows that (i) NORST is online (after initialization) and enjoys near-optimal values of tracking delay, lower bound on required delay between subspace change times, and of memory complexity; and (ii) it has a significantly improved worst-case outlier tolerance compared with all previous robust PCA or RST methods without requiring any model on how the outlier support is generated.} }
Endnote
%0 Conference Paper %T Nearly Optimal Robust Subspace Tracking %A Praneeth Narayanamurthy %A Namrata Vaswani %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-narayanamurthy18a %I PMLR %P 3701--3709 %U https://proceedings.mlr.press/v80/narayanamurthy18a.html %V 80 %X Robust subspace tracking (RST) can be simply understood as a dynamic (time-varying) extension of robust PCA. More precisely, it is the problem of tracking data lying in a fixed or slowly-changing low-dimensional subspace while being robust to sparse outliers. This work develops a recursive projected compressive sensing algorithm called “Nearly Optimal RST (NORST)”, and obtains one of the first guarantees for it. We show that NORST provably solves RST under weakened standard RPCA assumptions, slow subspace change, and a lower bound on (most) outlier magnitudes. Our guarantee shows that (i) NORST is online (after initialization) and enjoys near-optimal values of tracking delay, lower bound on required delay between subspace change times, and of memory complexity; and (ii) it has a significantly improved worst-case outlier tolerance compared with all previous robust PCA or RST methods without requiring any model on how the outlier support is generated.
APA
Narayanamurthy, P. & Vaswani, N.. (2018). Nearly Optimal Robust Subspace Tracking. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3701-3709 Available from https://proceedings.mlr.press/v80/narayanamurthy18a.html.

Related Material