Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares

Christian Kümmerle, Johannes Maly
June 2023
PDF Cite Code Poster Slides Link to Proceedings arXiv OpenReview

Abstract

We propose a new algorithm for the problem of recovering data that adheres to multiple, heterogeneous low-dimensional structures from linear observations. Focusing on data matrices that are simultaneously row-sparse and low-rank, we propose and analyze an iteratively reweighted least squares (IRLS) algorithm that is able to leverage both structures. In particular, it optimizes a combination of non-convex surrogates for row-sparsity and rank, a balancing of which is built into the algorithm. We prove locally quadratic convergence of the iterates to a simultaneously structured data matrix in a regime of minimal sample complexity (up to constants and a logarithmic factor), which is known to be impossible for a combination of convex surrogates. In experiments, we show that the IRLS method exhibits favorable empirical convergence, identifying simultaneously row-sparse and low-rank matrices from fewer measurements than state-of-the-art methods.

Type
Conference paper
Publication
In Advances in Neural Information Processing Systems 36 (NeurIPS 2023)
Non-Convex Optimization Simultaneous Parsimony Simultaneously Low-Rank and Row-Sparse Superlinear Convergence Iteratively Reweighted Least Squares Recovery Guarantees
Christian Kümmerle
Christian Kümmerle
Assistant Professor
School of Data, Mathematical, and Statistical Sciences
Department of Computer Science
Institute for Artificial Intelligence

I am passionate about the potential of AI and operations research for Lightning network operations and about efficiency gains within AI models that can be unlocked by combining smoothing, parsimony, structured optimization.