Document Open Access Logo

Smoothed Analysis of the Condition Number Under Low-Rank Perturbations

Authors Rikhav Shah, Sandeep Silwal

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.40.pdf
  • Filesize: 0.79 MB
  • 21 pages

Document Identifiers

Author Details

Rikhav Shah
  • University of California at Berkeley, CA, USA
Sandeep Silwal
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Silwal, Sandeep: Research supported by the NSF Graduate Research Fellowship under Grant No. 1122374.

Acknowledgements

We thank Sushruth Reddy and Samson Zhou for helpful conversations. We also thank Piotr Indyk and Arsen Vasilyan for helpful feedback on a draft of the paper.

Cite As Get BibTex

Rikhav Shah and Sandeep Silwal. Smoothed Analysis of the Condition Number Under Low-Rank Perturbations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 40:1-40:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.40

Abstract

Let M be an arbitrary n by n matrix of rank n-k. We study the condition number of M plus a low-rank perturbation UV^T where U, V are n by k random Gaussian matrices. Under some necessary assumptions, it is shown that M+UV^T is unlikely to have a large condition number. The main advantages of this kind of perturbation over the well-studied dense Gaussian perturbation, where every entry is independently perturbed, is the O(nk) cost to store U,V and the O(nk) increase in time complexity for performing the matrix-vector multiplication (M+UV^T)x. This improves the Ω(n²) space and time complexity increase required by a dense perturbation, which is especially burdensome if M is originally sparse. Our results also extend to the case where U and V have rank larger than k and to symmetric and complex settings. We also give an application to linear systems solving and perform some numerical experiments. Lastly, barriers in applying low-rank noise to other problems studied in the smoothed analysis framework are discussed.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Numerical analysis
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • Smoothed analysis
  • condition number
  • low rank noise

Metrics

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

Related Versions

References

  1. Thomas J Anastasio, Andrea K Barreiro, and Jared C Bronski. A geometric method for eigenvalue problems with low-rank perturbations. The Royal Society Publishing., 4, September 2017. URL: https://doi.org/10.1098/rsos.170390.
  2. D. Arthur and S. Vassilvitskii. Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 153-164, 2006. Google Scholar
  3. David Arthur, Bodo Manthey, and Heiko Röglin. Smoothed analysis of the k-means method. J. ACM, 58(5), 2011. URL: https://doi.org/10.1145/2027216.2027217.
  4. Anirban Basak and Mark Rudelson. Invertibility of sparse non-hermitian matrices. Advances in Mathematics, 310:426-483, 2017. URL: https://doi.org/10.1016/j.aim.2017.02.009.
  5. Avrim Blum and John Dunagan. Smoothed analysis of the perceptron algorithm for linear programming. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’02, page 905–914, USA, 2002. Society for Industrial and Applied Mathematics. Google Scholar
  6. E. J. Candes and Y. Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6):925-936, 2010. URL: https://doi.org/10.1109/JPROC.2009.2035722.
  7. E. J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2):489-509, 2006. URL: https://doi.org/10.1109/TIT.2005.862083.
  8. Zhuo Chen and D. Ellis. Speech enhancement by sparse, low-rank, and dictionary spectrogram decomposition. 2013 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, pages 1-4, 2013. Google Scholar
  9. Daniel Dadush and Sophie Huiberts. A friendly smoothed analysis of the simplex method. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 390–403, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3188745.3188826.
  10. Minh Dao, Yuanming Suo, Sang Chin, and Trac Tran. Structured sparse representation with low-rank interference. Conference Record - Asilomar Conference on Signals, Systems and Computers, 2015:106-110, April 2015. URL: https://doi.org/10.1109/ACSSC.2014.7094407.
  11. Alan Edelman. Eigenvalues and condition numbers of random matrices. SIAM Journal on Matrix Analysis and Applications, 9(4):543-560, 1988. URL: https://doi.org/10.1137/0609045.
  12. Friedrich Eisenbrand and Santosh S. Vempala. Geometric random edge. Math. Program., 164(1-2):325-339, 2017. URL: https://doi.org/10.1007/s10107-016-1089-0.
  13. Noam D. Elkies (https://mathoverflow.net/users/14830/noam-d elkies). Smallest non-zero eigenvalue of a (0,1) matrix. MathOverflow. URL:https://mathoverflow.net/q/157554 (version: 2017-04-13). URL: http://arxiv.org/abs/https://mathoverflow.net/q/157554.
  14. V. Klee, G.J. Minty, and WASHINGTON UNIV SEATTLE Dept. of MATHEMATICS. HOW GOOD IS THE SIMPLEX ALGORITHM. Defense Technical Information Center, 1970. URL: https://books.google.com/books?id=R843OAAACAAJ.
  15. X. Liu, M. Tanaka, and M. Okutomi. Practical signal-dependent noise parameter estimation from a single noisy image. IEEE Transactions on Image Processing, 23(10):4361-4371, 2014. URL: https://doi.org/10.1109/TIP.2014.2347204.
  16. Bodo Manthey and Heiko Raglin. Smoothed analysis: Analysis of algorithms beyond worst case. it - Information Technology, 53(6):280-286, 2011. URL: https://doi.org/10.1524/itit.2011.0654.
  17. Bodo Manthey and Rianne Veenstra. Smoothed analysis of the 2-opt heuristic for the tsp: Polynomial bounds for gaussian noise. In Leizhen Cai, Siu-Wing Cheng, and Tak-Wah Lam, editors, Algorithms and Computation, pages 579-589, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  18. Morteza Mardani, Gonzalo Mateos, and G.B. Giannakis. Recovery of low-rank plus compressed sparse matrices with application to unveiling traffic anomalies. IEEE Transactions on Information Theory, 59, April 2012. Google Scholar
  19. Sean O'Rourke, Van Vu, and Ke Wang. Random perturbation of low rank matrices: Improving classical bounds. Linear Algebra and its Applications, 540:26-59, 2018. URL: https://doi.org/10.1016/j.laa.2017.11.014.
  20. Richard Peng and Santosh Vempala. Solving sparse linear systems faster than matrix multiplication. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '21, page 504–521, USA, 2021. Society for Industrial and Applied Mathematics. Google Scholar
  21. Mark Rudelson and Roman Vershynin. Smallest singular value of a random rectangular matrix. Communications on Pure and Applied Mathematics, 62(12):1707-1739, 2009. URL: https://doi.org/10.1002/cpa.20294.
  22. Arvind Sankar, Daniel A. Spielman, and Shang-Hua Teng. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications, 28(2):446-476, 2006. URL: https://doi.org/10.1137/S0895479803436202.
  23. Yoav Seginer. The expected norm of random matrices. Combinatorics, Probability and Computing, 9:149-166, March 2000. URL: https://doi.org/10.1017/S096354830000420X.
  24. Daniel A. Spielman and Shang hua Teng. Smoothed analysis: an attempt to explain the behavior of algorithms in practice. COMMUN. ACM, 2009. Google Scholar
  25. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385–463, 2004. URL: https://doi.org/10.1145/990308.990310.
  26. Moeller Steen, Sebastian Weingartner, and Mehmet Akcakaya. Multi-scale locally low-rank noise reduction for high-resolution dynamic quantitative cardiac mri. Annual International Conference of the IEEE Engineering in Medicine and Biology Society., 2017:1473-1476, July 2017. URL: https://doi.org/10.1109/EMBC.2017.8037113.
  27. Terence Tao and Van Vu. Smooth analysis of the condition number and the least singular value. Mathematics of Computation, 79(272):2333-2352, 2010. URL: http://www.jstor.org/stable/20779147.
  28. Vu Tau. Random matrices: the distribution of the smallest singular values. Geometric and Functional Analysis, 20:260-297, March 2010. URL: https://doi.org/10.1007/s00039-010-0057-8.
  29. Shang-Hua Teng. Smoothed analysis of algorithms and heuristics. In Lusheng Wang, editor, Computing and Combinatorics, pages 10-11, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  30. C Tomasi and T. Kanade. Shape and motion from image streams under orthography: a factorization method. Int Journal of Computer Vision, 9:137-154, 1992. URL: https://doi.org/10.1007/BF00129684.
  31. Lloyd N. Trefethen and David Ill. Bau. Numerical linear algebra. SIAM Society for Industrial and Applied Mathematics, 2000. Google Scholar
  32. Van H. Vu and Terence Tao. The condition number of a randomly perturbed matrix. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 248–255, New York, NY, USA, 2007. Association for Computing Machinery. URL: https://doi.org/10.1145/1250790.1250828.
  33. Karl Werner and Magnus Jansson. Parameter estimation for reduced-rank multivariate linear regressions in the presence of correlated noise. In Conference Record of the Asilomar Conference on Signals, Systems and Computers, volume 2, pages 2101-2105 Vol.2, December 2003. Google Scholar
  34. Wikipedia contributors. Product distribution - Wikipedia, the free encyclopedia, 2020. [Online; accessed 18-August-2020]. URL: https://en.wikipedia.org/w/index.php?title=Product_distribution&oldid=970273508.
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 About DROPS Imprint Privacy Contact