Document Open Access Logo

Parameterized Complexity of PCA (Invited Talk)

Authors Fedor V. Fomin, Petr A. Golovach, Kirill Simonov

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.1.pdf
  • Filesize: 423 kB
  • 5 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • Department of Informatics, University of Bergen, Norway
Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway
Kirill Simonov
  • Department of Informatics, University of Bergen, Norway

Funding

This work is supported by the Research Council of Norway via the project "MULTIVAL".

Cite AsGet BibTex

Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov. Parameterized Complexity of PCA (Invited Talk). In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 1:1-1:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SWAT.2020.1

Abstract

We discuss some recent progress in the study of Principal Component Analysis (PCA) from the perspective of Parameterized Complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • parameterized complexity
  • Robust PCA
  • outlier detection

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics). Springer-Verlag, Berlin, Heidelberg, 2006. Google Scholar
  2. Thierry Bouwmans, Necdet Serhat Aybat, and El-hadi Zahzah. Handbook of robust low-rank and sparse matrix decomposition: Applications in image and video processing. Chapman and Hall/CRC, 2016. Google Scholar
  3. Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? J. ACM, 58(3):11:1-11:37, 2011. URL: http://dx.doi.org/10.1145/1970392.1970395.
  4. Venkat Chandrasekaran, Sujay Sanghavi, Pablo A. Parrilo, and Alan S. Willsky. Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization, 21(2):572-596, 2011. URL: http://dx.doi.org/10.1137/090761793.
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  6. Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou. On low rank approximation of binary matrices. CoRR, abs/1511.01699, 2015. URL: http://arxiv.org/abs/1511.01699.
  7. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness. Proceedings of the 21st Manitoba Conference on Numerical Mathematics and Computing. Congr. Numer., 87:161-178, 1992. Google Scholar
  8. Rodney G. Downey and Michael R. Fellows. Parameterized complexity. Springer-Verlag, New York, 1999. Google Scholar
  9. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  10. Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211-218, 1936. Google Scholar
  11. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2006. Google Scholar
  12. Fedor V. Fomin, Daniel Lokshtanov, Syed Mohammad Meesum, Saket Saurabh, and Meirav Zehavi. Matrix rigidity from the viewpoint of parameterized complexity. SIAM J. Discrete Math., 32(2):966-985, 2018. URL: http://dx.doi.org/10.1137/17M112258X.
  13. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization. Theory of Parameterized Preprocessing. Cambridge University Press, 2019. Google Scholar
  14. Nicolas Gillis and Stephen A. Vavasis. On the complexity of robust PCA and 𝓁₁-norm low-rank matrix approximation. CoRR, abs/1509.09236, 2015. URL: http://arxiv.org/abs/1509.09236, URL: http://arxiv.org/abs/1509.09236.
  15. Nicolas Gillis and Stephen A. Vavasis. On the complexity of robust PCA and 𝓁₁-norm low-rank matrix approximation. Math. Oper. Res., 43(4):1072-1084, 2018. URL: http://dx.doi.org/10.1287/moor.2017.0895.
  16. Dmitry Grigoriev. Using the notions of separability and independence for proving the lower bounds on the circuit complexity (in russian). Notes of the Leningrad branch of the Steklov Mathematical Institute, Nauka, 1976. Google Scholar
  17. Dmitry Grigoriev. Using the notions of separability and independence for proving the lower bounds on the circuit complexity. Journal of Soviet Math., 14(5):1450-1456, 1980. Google Scholar
  18. Moritz Hardt and Ankur Moitra. Algorithms and hardness for robust subspace recovery. In Proceedings of the 26th Annual Conference on Learning Theory (COLT), volume 30 of JMLR Proceedings, pages 354-375. JMLR.org, 2013. Google Scholar
  19. Harold Hotelling. Analysis of a complex of statistical variables into principal components. Journal of educational psychology, 24(6):417, 1933. Google Scholar
  20. Gilad Lerman and Tyler Maunu. An overview of robust subspace recovery. Proceedings of the IEEE, 106(8):1380-1410, 2018. Google Scholar
  21. Rolf Niedermeier. Invitation to fixed-parameter algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, 2006. Google Scholar
  22. Karl Pearson. LIII. on lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559-572, 1901. Google Scholar
  23. Tim Roughgarden, editor. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020. Google Scholar
  24. Kirill Simonov, Fedor V. Fomin, Petr A. Golovach, and Fahad Panolan. Refined complexity of PCA with outliers. In Proceedings of the 36th International Conference on Machine Learning, (ICML), volume 97, pages 5818-5826. PMLR, 2019. URL: http://proceedings.mlr.press/v97/simonov19a.html.
  25. L G Valiant. Graph-theoretic arguments in low-level complexity. In MFCS, pages 162-176, 1977. Google Scholar
  26. Namrata Vaswani and Praneeth Narayanamurthy. Static and dynamic robust PCA and matrix completion: A review. Proceedings of the IEEE, 106(8):1359-1379, 2018. URL: http://dx.doi.org/10.1109/JPROC.2018.2844126.
  27. John Wright, Arvind Ganesh, Shankar R. Rao, YiGang Peng, and Yi Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. In Proceedings of 23rd Annual Conference on Neural Information Processing Systems (NIPS), pages 2080-2088. Curran Associates, Inc., 2009. URL: http://papers.nips.cc/paper/3704-robust-principal-component-analysis-exact-recovery-of-corrupted-low-rank-matrices-via-convex-optimization.
  28. Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust PCA via outlier pursuit. In Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS), pages 2496-2504. Curran Associates, Inc., 2010. URL: http://papers.nips.cc/paper/4005-robust-pca-via-outlier-pursuit.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact