Principal submatrices, restricted invertibility and a quantitative Gauss-Lucas theorem
This work offers a new perspective on restricted invertibility with algorithmic constructions and a quantitative bound for the Gauss-Lucas theorem, but the results are incremental refinements of known techniques.
The authors provide an alternate proof of restricted invertibility results using principal submatrices, showing that well-conditioned column submatrices can be found up to the modified stable rank. They also derive a quantitative Gauss-Lucas theorem: for any degree n polynomial p and c ≥ 1/2, the area of the convex hull of the roots of p^{(cn)} is at most 4(c - c^2) times that of p.
We apply the techniques developed by Marcus, Spielman and Srivastava, working with principal submatrices in place of rank $1$ decompositions to give an alternate proof of their results on restricted invertibility. We show that one can find well conditioned column submatrices all the way upto the so called modified stable rank. All constructions are algorithmic. A byproduct of these results is an interesting quantitative version of the classical Gauss-Lucas theorem on the critical points of complex polynomials. We show that for any degree $n$ polynomial $p$ and any $c \geq \frac{1}{2}$, the area of the convex hull of the roots of $p^{(cn)}$ is at most $4(c-c^2)$ that of the area of the convex hull of the roots of $p$.