Smooth Analysis of the Condition Number and the Least Singular Value

Abstract

A few years ago, Spielman and Teng initiated the study of Smooth analysis of the condition number and the least singular value of a matrix. Let x be a complex variable with mean zero and bounded variance. Let N n be the random matrix of sie n whose entries are iid copies of x and M a deterministic matrix of the same size. The goal of smooth analysis is to estimate the condition number and the least singular value of M + N n . Spielman and Teng considered the case when x is gaussian. We are going to study the general case when x is arbitrary. Our investigation reveals a new and interesting fact that, unlike the gaussian case, in the general case the "core" matrix M does play a role in the tail bounds for the least singular value of M + N n . Consequently, our estimate involves the norm ∥ M ∥ and it is a challenging question to determine the right magnitude of this involvement. When ∥ M ∥ is relatively small, our estimate is nearly optimal and extends or refines several existing result.

Locations

• Lecture notes in computer science - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF
• DataCite API - View
• Lecture notes in computer science - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF
• DataCite API - View
• Lecture notes in computer science - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF
• DataCite API - View