A characterization of the distance to infeasibility under block-structured perturbations

We discuss several generalizations of the classical Eckart and Young identity. We show that a natural extension of this identity holds for rectangular matrices defining conic systems of constraints, and for perturbations restricted to a particular block structure, such as those determined by a sparsity pattern. Our results extend and unify the classical Eckart and Young identity, Renegar's characterization of the distance to infeasibility [Math. Programming 70 (1995), 279--351], Rohn's characterization of the componentwise distance to singularity [Linear Algebra Appl. 126 (1989), 39--78], and Cheung and Cucker's characterization of the normalized distance to ill-posedness [Math. Programming 91 (2001), 163--174].

Citation

Linear Algebra and its Applications 370 (2003) 193--216.