Projecting onto space of matrices with spectral radius less than one

Question

Consider the space

$$ S = \left\{ A \in \mathbb{R}^{n \times n} : \mathrm{SpectralRadius}(|A|) \leq 1 \right\}$$

where $|A|$ is the entry-wise absolute value. Given a matrix $M \in \mathbb{R}^{n\times n}$ such that $M \not \in S$. Is there a way to solve

$$\arg\min_{\hat M \in S} \Vert M - \hat M \Vert$$ for some matrix norm $\Vert \cdot \Vert$? That is, is there a (hopefully somewhat simple) operator that projects onto $S$ for some matrix norm?

For context, I'm interested in optimising a function $f:\mathbb{R}^{n\times n} \rightarrow \mathbb{R}$ over this space using stochastic gradient descent. This means that I'd have to perform this projection after every optimisation step. I know that in general $S$ is non-convex and so I won't have any guarantees.

---

Edit: I'm interested in the case with the absolute value. However, someone noted in a comment that the scenario may simplify if we consider the space $$S' = \left\{ A \in \mathbb{R}^{n \times n} : \mathrm{SpectralRadius}(A) \leq 1 \right\}$$ Maybe to start, is there a simpler answer in this case?

Answer 1

For the version without the absolute value, a colleague and I published a few months ago an algorithm to solve that optimization problem and other related ones (the problem you need is called "Schur stable" case in the paper). Some competitors are mentioned in the introduction and in the section with numerical experiments, but I believe ours is the fastest algorithm available as of today. It is not too simple as it relies on optimization on manifolds, however this is not a simple problem in general: the constraint on the eigenvalues is non-smooth and tricky to handle numerically.

We have also published on https://github.com/fph/nearest-omega-stable some proof-of-concept Matlab code that you can use.

Answer 2

For the problem without absolute value and with the spectral norm instead of spectral radius, hard-thresholding the singular values of $\mathbf{M}$ yields a matrix $\mathbf{X}$ that is its best approximation with respect to the Frobenius norm, i.e. the solution to: $$ \begin{array}{l} \mbox{minimize } \Vert \mathbf{X}-\mathbf{M} \Vert_F \\ \mbox{subject to } \Vert \mathbf{X} \Vert_2 \le \lambda . \end{array} $$

I am sure there are several references for this for this but I have found the following lemma and its proof in [1].

Lemma 2.2 (Minimization of the Frobenius norm under the spectral norm constraint). Assume the SVD of $\mathbf{M}$ is given by $\mathbf{M=U\Sigma V^*}$ where $\mathbf{\Sigma}=\mbox{diag}(\sigma_1,..,\sigma_n)$. Then, the matrix $\mathbf{X}$, which minimizes $\Vert \mathbf{X}-\mathbf{M} \Vert_F$ such that $\Vert \mathbf{X} \Vert_2 \le \lambda$, is given by $\mathbf{X=U\tilde{\Sigma}V^*}$ where $\tilde{\sigma_i}$ are the singular values of $\tilde{\Sigma}$ and $\tilde{\sigma_i}=\min(\sigma_i, \lambda), i=1, \ldots k, ~k \le n$.

I hope this result (and possibly even more the proof) is a good start to solve your original problem.

[1] Shabat, G., & Averbuch, A. (2012). Interest zone matrix approximation. The Electronic Journal of Linear Algebra, 23, 678-702. DOI:10.13001/1081-3810.1551