Fall 2017

On Sparse Generalized Inverses by LP, Not SDP, and Local Search

Thursday, December 13th, 2018 9:30 am10:15 am

Add to Calendar


Jon Lee (University of Michigan)

The Moore-Penrose Pseudoinverse (MPP) is a key tool in data analysis. Eg., it can be used to solve least-squares problems. But the MPP is typically dense, and with very large data sets, we may be content with an approximation of MPP that is much sparser. When we have a use case where we need to multiply many vectors by the MPP, we may be willing to put in substantial effort to get a sparse approximation. We use linear programming and (not) semidefinite programming to define and calculate various sparse generalized inverses, and we use a local-search scheme to derive a relevant polynomial-time approximation algorithm. This is joint work with Marcia Fampa (UFRJ) and Victor Fuentes (UM).