2026-07-22T05:41:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14733 2024-03-06T10:54:46Z ddc:004 open_access

Smoothed Analysis of the Condition Number Under Low-Rank Perturbations Shah, Rikhav Silwal, Sandeep Smoothed analysis condition number low rank noise 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rikhav Shah and Sandeep Silwal 2021 Is Part Of LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2021.40 urn:nbn:de:0030-drops-147332 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.40 eng https://creativecommons.org/licenses/by/4.0/legalcode