# Maximize the Euclidean norm of a matrix times a vector on unit sub-spheres

For $X = (x_1^T,\ldots,x_N^T)^T \in \mathbb{R}^{Nm \times 1}$, where $x_i \in \mathbb{R}^{m \times 1}$ for $i \in \{1,\ldots,N\}$, $A \in \mathbb{R}^{r \times Nm}$, and $r \geq Nm$, I want to obtain a closed form solution of

$$\max_{X \in \mathbb{R}^{Nm}}\{\|AX\|: \|x_i\|^2=1\}$$

where $\|\cdot\|$ denotes the Euclidean norm. I know how to find a closed form solution of

$$\max_{X \in \mathbb{R}^{Nm}}\{\|AX\|: \|X\|^2=1\}$$

that is, when $\|X\|^2=1$. However, I do not see how to solve it when we have $\|x_i\|^2=1$.

• Do you mean $\mathbb{R}^{N \times m}$? It is a big difference from you wrote.
– Royi
Aug 2, 2017 at 13:42
• No. The stacked vector $X$ is $Nm$-dimensional Aug 2, 2017 at 13:45
• I edited the question. I hope it is clearer now. Aug 2, 2017 at 13:50
• So $X$ is a vector. Don't use Capitalized letter.
– Royi
Aug 2, 2017 at 13:51
• Aug 4, 2017 at 1:02

$$\mathrm A \mathrm x = \begin{bmatrix} \mathrm A_1 & \mathrm A_2 & \cdots & \mathrm A_n\end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}$$

where $\mathrm x_1, \mathrm x_2, \dots, \mathrm x_n \in \mathbb R^m$ are the optimization variables. Hence,

$$\| \mathrm A \mathrm x \|_2^2 = \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}^\top \begin{bmatrix} \mathrm A_1^\top \mathrm A_1 & \mathrm A_1^\top \mathrm A_2 & \cdots & \mathrm A_1^\top \mathrm A_n\\ \mathrm A_2^\top \mathrm A_1 & \mathrm A_2^\top \mathrm A_2 & \cdots & \mathrm A_2^\top \mathrm A_n\\ \vdots & \vdots & \ddots & \vdots\\\mathrm A_n^\top \mathrm A_1 & \mathrm A_n^\top \mathrm A_2 & \cdots & \mathrm A_n^\top \mathrm A_n\\ \end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}$$

$$\begin{array}{ll} \text{maximize} & \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}^\top \begin{bmatrix} \mathrm A_1^\top \mathrm A_1 & \mathrm A_1^\top \mathrm A_2 & \cdots & \mathrm A_1^\top \mathrm A_n\\ \mathrm A_2^\top \mathrm A_1 & \mathrm A_2^\top \mathrm A_2 & \cdots & \mathrm A_2^\top \mathrm A_n\\ \vdots & \vdots & \ddots & \vdots\\\mathrm A_n^\top \mathrm A_1 & \mathrm A_n^\top \mathrm A_2 & \cdots & \mathrm A_n^\top \mathrm A_n\\ \end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}\\ \text{subject to} & \| \mathrm x_1 \|_2^2 = 1\\ & \| \mathrm x_2 \|_2^2 = 1\\ & \qquad\vdots \\ & \| \mathrm x_n \|_2^2 = 1 \end{array}$$

Let the Lagrangian be

$$\mathcal L (\mathrm x_1, \dots, \mathrm x_n, \mu_1, \dots, \mu_n) := \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}^\top \begin{bmatrix} \mathrm A_1^\top \mathrm A_1 & \mathrm A_1^\top \mathrm A_2 & \cdots & \mathrm A_1^\top \mathrm A_n\\ \mathrm A_2^\top \mathrm A_1 & \mathrm A_2^\top \mathrm A_2 & \cdots & \mathrm A_2^\top \mathrm A_n\\ \vdots & \vdots & \ddots & \vdots\\\mathrm A_n^\top \mathrm A_1 & \mathrm A_n^\top \mathrm A_2 & \cdots & \mathrm A_n^\top \mathrm A_n\\ \end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix} - \sum_{k=1}^n \mu_k \left( \| \mathrm x_k \|_2^2 - 1 \right)$$

Taking all the partial derivatives of the Lagrangian and finding where they vanish, we then obtain the following homogeneous linear system

$$\begin{bmatrix} \mathrm A_1^\top \mathrm A_1 - \mu_1 \mathrm I_m & \mathrm A_1^\top \mathrm A_2 & \cdots & \mathrm A_1^\top \mathrm A_n\\ \mathrm A_2^\top \mathrm A_1 & \mathrm A_2^\top \mathrm A_2 - \mu_2 \mathrm I_m & \cdots & \mathrm A_2^\top \mathrm A_n\\ \vdots & \vdots & \ddots & \vdots\\\mathrm A_n^\top \mathrm A_1 & \mathrm A_n^\top \mathrm A_2 & \cdots & \mathrm A_n^\top \mathrm A_n - \mu_n \mathrm I_m \end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix} = \begin{bmatrix} 0_m\\ 0_m\\ \vdots \\ 0_m\end{bmatrix}$$

and the equality constraints $\| \mathrm x_1 \|_2^2 = \| \mathrm x_2 \|_2^2 = \cdots = \| \mathrm x_n \|_2^2 = 1$. To satisfy the $n$ equality constraints, we cannot have just the solution $\mathrm x = 0_{mn}$. Thus, the matrix above must be singular, i.e.,

$$\det \begin{bmatrix} \mathrm A_1^\top \mathrm A_1 - \mu_1 \mathrm I_m & \mathrm A_1^\top \mathrm A_2 & \cdots & \mathrm A_1^\top \mathrm A_n\\ \mathrm A_2^\top \mathrm A_1 & \mathrm A_2^\top \mathrm A_2 - \mu_2 \mathrm I_m & \cdots & \mathrm A_2^\top \mathrm A_n\\ \vdots & \vdots & \ddots & \vdots\\\mathrm A_n^\top \mathrm A_1 & \mathrm A_n^\top \mathrm A_2 & \cdots & \mathrm A_n^\top \mathrm A_n - \mu_n \mathrm I_m \end{bmatrix} = 0$$

which produces a polynomial equation of degree $m n$ in the $n$ Lagrange multipliers $\mu_1, \mu_2, \dots, \mu_n$.