2023/06/08 by Christian Kümmerle, Kümmerle, Christian, Johannes Maly +1 · 1 citation
Computer Science · #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Neural Networks and Applications #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2306.04961
openalex publication_date 2023/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. Code is available at https://github.com/ckuemmerle/simirls.