Painless breakups -- efficient demixing of low rank matrices (Q1710648)

This manuscript deals with a low rank demixing problem, where the signals to be separated all have similar properties, that is, they are all low rank matrices. Assume we are given a sum of linear measurements \[ y=\sum_{k=1}^s \mathcal{A}_k(X_k), \] where \(\{\mathcal{A}_k \}_{k=1}^s\) is a set of linear operators from \(n \times n\) matrices to \(m\)-dimensional vectors and \(\{X_k \}_{k=1}^s\) are unknown rank-\(r\) matrices. The aim of this paper is to analyze when and under which conditions it is possible to extract (demix) the individual matrices \(X_k\) from the single measurement vector \(y\). And when this demixing is numerically efficient? The authors present two computationally efficient algorithms based on hard thresholding to solve this low rank demixing problem. They introduce an Amalgam-Restricted Isometry Property which is suitable for demixing problems and prove that under appropriate conditions these algorithms are guaranteed to converge to the correct solution at a linear rate. These algorithms can solve the nonlinear low rank matrix demixing problem without resorting to convex optimization, and meanwhile to provide competitive theoretical recovery guarantees. The authors test the empirical performance of the proposed algorithms on simulated problems an on examples from quantum tomography. Finally, the authors present some potential future directions and applications of the proposed algorithms.