## Are there perturbations that preserve incoherence and give nicely conditioned “submatrices”?

### April 14, 2012

Let $$\mat{P}_{\mathcal{U}}$$ denote the projection unto a $$k$$-dimensional subspace of $$\C^{n}.$$ We say $$\mathcal{U}$$ is $$\mu$$-coherent if $$(\mat{P}_{\mathcal{U}})_{ii} \leq \mu \frac{k}{n}$$ for all $$i = 1, \ldots, n.$$

Let $$\mat{A} \in \C^{n \times n}$$ be a SPSD matrix whose top $$k$$-dimensional invariant subspace is $$\mu$$-coherent. Given $$\delta > 0$$ and $$\mat{S} \in \C^{n \times \ell}$$, where $$k < \ell \ll n,$$  is there a matrix $$\mat{E}_{\delta,\mat{S}} \in \C^{n \times n}$$ such that

1. $$\hat{\mat{A}} := \mat{A} + \mat{E}_{\delta,\mat{S}}$$ is SPSD,
2. The top $$k$$-dimensional invariant subspace of $$\hat{\mat{A}}$$ is also $$\mu$$-coherent,
3. $$\|\hat{\mat{A}} – \mat{A}\|_2 < \delta$$, and
4. $$\mat{S}^t \hat{\mat{A}} \mat{S} \succeq \delta \cdot \mat{I}$$ ?

It’d be fine if instead of (2) holding, the coherence of the top $$k$$-dimensional invariant subspace of $$\hat{\mat{A}}$$ is slightly larger than that of $$\mat{A}$$.