Least squares problem with constraints on the absolute value of the eigenvalues

Question

I am trying to perform an estimation of $x$, such that $\|Ax-b\|^2$ is minimized, subject to the constraint on the eigenvalues $\max(|\lambda(x)|) \leq 1$. I was wondering the following:

1. What would be a sufficient condition for this to be true?
2. What would be a necessary condition?
3. Is there a way to implement this using convex optimization?

I am talking about the magnitude of the eigenvalues. This is equivalent to saying that all eigenvalues lie within the unit disc (on real/imaginary plane).

Description of the Variables:

A is a NxN matrix x is a Nx1 vector b is a Nx1 vector

However, this is because my problem is vectorized, so I solve it in this fashion. My final data estimate is x reshaped into an mxm matrix, where m*m = N. So I want this x_reshaped matrix to have eigenvalues less then 1.

Answer 1

If I understand the question correctly, we have the constrained least-squares problem

$$\begin{array}{ll} \text{minimize} & \|\mathrm A \mathrm X - \mathrm B\|_F^2\\ \text{subject to} & \rho(\mathrm X) \leq 1\end{array}$$

where $\mathrm A, \mathrm B \in \mathbb{R}^{m \times n}$ are given and $\rho (\cdot)$ denotes the spectral radius. Using a strict inequality instead

$$\begin{array}{ll} \text{minimize} & \|\mathrm A \mathrm X - \mathrm B\|_F^2\\ \text{subject to} & \rho(\mathrm X) < 1\end{array}$$

If $\rho(\mathrm X) < 1$, then the origin of the discrete-time linear dynamical system $\eta_{k+1} = \mathrm X \eta_{k}$ is globally asymptotically stable (GAS). Let $V (\eta) := \eta^T \mathrm P \eta$ be a Lyapunov function, where $\mathrm P \succ \mathrm O_n$ is to be determined. Hence,

$$(\forall \eta \neq 0_n) (V (\mathrm X \eta) - V (\eta) < 0) \Longleftrightarrow (\forall \eta \neq 0_n) (\eta^T (\mathrm X^T \mathrm P \mathrm X - \mathrm P) \, \eta < 0) \Longleftrightarrow \mathrm X^T \mathrm P \mathrm X - \mathrm P \prec \mathrm O_n$$

where the matrix inequality $\mathrm X^T \mathrm P \mathrm X - \mathrm P \prec \mathrm O_n$ can be rewritten as $\mathrm P - \mathrm X^T \mathrm P \mathrm X \succ \mathrm O_n$. Thus, we have the following optimization problem in $\mathrm X$ and $\mathrm P$

$$\begin{array}{ll} \text{minimize} & \|\mathrm A \mathrm X - \mathrm B\|_F^2\\ \text{subject to} & \mathrm P \succ \mathrm O_n\\ & \mathrm P - \mathrm X^T \mathrm P \mathrm X \succ \mathrm O_n\end{array}$$

Note that $\mathrm P - \mathrm X^T \mathrm P \mathrm X \succ \mathrm O_n$ is not a linear matrix inequality (LMI). How can one solve this?