betaFeedback

WorksMathematics

Row-sparse ah-symmetric reflexive generalized inverses with a few extra rows: local search with approximation guarantees

Abstract

For a rank-rr matrix A∈Rm×nA\in\mathbb{R}^{m\times n}, ah-symmetric reflexive generalized inverses HH with few nonzero rows give least-squares solutions that are fast to evaluate and use few variables. A known determinant-based local search finds one with exactly rr nonzero rows and 2,1-norm within an essentially tight factor rr of the minimum at an exact local optimum. We let the nonzero rows of HH lie in a set KK of k≥rk\ge r indices and study how to choose KK. We bound the loss of this restriction (restricted over unrestricted minimum 2,1-norm) by a simple geometric certificate and establish that a local search maximizing the squared rank-rr volume of the corresponding columns of AA gives loss at most k(r+εk)/(k−r+1)\sqrt{k(r+εk)/(k-r+1)}, where 1+ε1+ε is the swap tolerance. With ε=0ε=0 this is rr at k=rk=r and less than 2r\sqrt{2r} for k≥2rk\ge2r; with ε=1/kε=1/k the search runs in polynomial time on rational data. The same support yields an ah-symmetric reflexive generalized inverse with spectral norm within a factor 1+(n−k)(r+εk)/(k−r+1)\sqrt{1+(n-k)(r+εk)/(k-r+1)} of that of the Moore-Penrose pseudoinverse. The loss guarantees hold for every norm on the rows. In general, our certificate bound is tight up to a factor depending only on k/rk/r, and on some instances, for a suitable row norm, so is the loss bound; for the 2,1-norm, however, the certificate can overestimate the loss by a factor r\sqrt r. The local search is the Fedorov exchange algorithm of 0/1 D-optimal design; this yields a fast implementation and, via the Kiefer-Wolfowitz theorem, supports of at most r(r+1)/2+1r(r+1)/2+1 rows with certificate at most r\sqrt r, best possible in general. On instances from earlier work, the observed loss is far below the guarantee, and the method matches two ADMM heuristics when few rows are removed and otherwise gives 2,1-norms up to 27% smaller, one to two orders of magnitude faster.

Paper details

vlnc:W_u38yqjgk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude

View statement
Looking for related papers…