Sparse quadratic forms and their geometric applications [following Batson, Spielman, and Srivastava].

MaRDI QIDQ4913077zbMATH OpenFDO

Authors Assaf Naor

Publication date 3 April 2013

Full work available at URL https://arxiv.org/abs/1101.4324

zbMATH Keywords

Bourgain-Tzafriri restricted invertibility principledimensionality reductionJohn decompositionssparse quadratic forms

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Theory of matrix inversion and generalized inverses (15A09) Quadratic and bilinear forms, inner products (15A63)

Abstract: We survey the work of Batson, Spielman and Srivastava on graph sparsification, and we describe some of its recently discovered geometric applications.

Recommendations

• An elementary proof of the restricted invertibility theorem
• Interlacing families. III: Sharper restricted invertibility estimates
• Sparser Johnson-Lindenstrauss transforms
• John's decompositions: Selecting a large part

Cited in

(6)

• On a new method for controlling the entire spectrum in the problem of column subset selection
• Graphs, vectors, and matrices
• Enhancing pure-pixel identification performance via preconditioning
• Restricted invertibility revisited
• Bounds on Dimension Reduction in the Nuclear Norm
• On exponential frames near the critical density

This page was built for publication: Sparse quadratic forms and their geometric applications [following Batson, Spielman, and Srivastava].

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4913077)