Codes and Expansions (CodEx) Seminar

Andreas Tillmann (TU Clausthal):
A Discrete Optimization Approach to Matrix Sparsification

The sparsity of matrices can be exploited in various applications, e.g., to speed up the solution of linear systems or in second-order optimization algorithms. This motivates considering the matrix sparsification problem (MS), in which we seek an equivalent representation of a given matrix with as few nonzero entries as possible. While MS and the equivalent sparse nullspace basis problem have been of interest for decades, the only known solution approaches appear to be heuristics or methods relying on restrictive assumptions that may be unlikely to hold in practice. We propose a sequential mixed-integer linear programming algorithm for matrix sparsification that leverages relations to matroid theory, discuss connections to a machine learning task known as dictionary learning, and show some numerical results of the ongoing implementation work.