A characterization of the distance to infeasibility under block-structured perturbations (Q1405035): Difference between revisions

Generalizations of the Eckart and Young identity for a square non-singular matrix \(A\) \[ \inf \left\{ \|\Delta A \|: A+ \Delta A \;\text{ is \;singular} \right\} =\frac{1}{\|A^{-1}\|} \] characterizing the distance to singularity are discussed. This identity gives a connection between the conditioning of \(A\) and the distance to ill-posedness of the system of equations \(Ax=b\) for any \(b \in \mathbb {R}^{n}\) and has a natural extension to conic linear systems. It is shown that suitable extension of the Eckart and Young identity exists for the distance to infeasibility of conic systems, when the perturbations are restricted to a predefined block structure such as low-rank perturbations, horizontal block-structured perturbations and other special types of perturbations. The main result of the paper extends and unifies in natural way the previously known \textit{J. Renegar}'s characterization of the distance to infeasibility [Math. Program. 70, 279-351 (1995; Zbl 0855.90085)], \textit{J. Rohn}'s characterization of the componentwise distance to singularity [Linear Algebra Appl. 126, 39-78 (1989; Zbl 0712.65029)] and \textit{D. Cheung} and \textit{F. Cucker}'s characterization of the normalized distance to ill-posedness [Math. Program. 91, 163-174 (2001; Zbl 1072.90564)]. The key technique in establishing this general characterization is a low-rank construction of \(\Delta A\).