STPM - Sparce Approximation of PSD Matrices

STPM - Some Questions Regarding Arithmetic Circuits - Srikanth Srinivasan

Nikhil Srivastava
Institute for Advanced Study
September 30, 2010

I will discuss the problem of approximating a given positive semidefinite matrix A , written as a sum of outer products $vv^T$ , by a much shorter weighted sum in the same outer products. I will then mention an application to sparsification of finite undirected graphs.