Finding some $\textbf{x}$ that maximises $\left\|\textbf{A}\textbf{x}\right\|_2$

58 Views Asked by At

Let $\textbf{M}\in \mathbb{R}^{n, n} $ be a symmetric positive definite matrix and $\textbf{A}\in \mathbb{R}^{m, n} $. Find \begin{align*} \text{argmax}_{\textbf{x}\in S} \left\|\textbf{A}\textbf{x}\right\|_{2}, \quad S=\left\{\textbf{x}\in \mathbb{R}^{n} \ \middle|\ \textbf{x}^{\mathsf{T}}\textbf{M}\textbf{x}=1\right\} .\end{align*}

My approach so far: Since $\textbf{M}$ is spd. there exists some eigendecomposition $\textbf{M}=\textbf{V}\Lambda \textbf{V}^{\mathsf{T}} $ with $\textbf{V}\in \mathbb{R}^{n, n} $ being orthogonal. Hence any minimiser $\textbf{x}$ must satisfy \begin{align*} \textbf{x}^{\mathsf{T}}\textbf{V}\Lambda \textbf{V}^{\mathsf{T}}\textbf{x}=1 \iff \left(\Lambda ^{-\frac{1}{2}} \textbf{V}^{\mathsf{T}}\textbf{x} \right) ^{\mathsf{T}} \left( \Lambda ^{-\frac{1}{2}} \textbf{V}^{\mathsf{T}} \textbf{x} \right) =1 \iff \left\|\Lambda^{-\frac{1}{2}} \textbf{V}^{\mathsf{T}}\textbf{x}\right\|_{2} =1 .\end{align*} Note that the rows of $\textbf{V}^{\mathsf{T}}$ span $\mathcal{N}\left(\textbf{M}\right) ^{\perp } $ since $\mathcal{N}\left(\textbf{M}\right) =\left\{\mathbf{O}\right\} $.

Now, considering the SVD of $\textbf{A}=\textbf{U}\Sigma \textbf{P}^{\mathsf{T}} $ \begin{align*} \text{argmax}_{\textbf{x}\in S} \left\|\textbf{A}\textbf{x}\right\|_{2} = \text{argmax}_{\textbf{x}\in S} \left\|\textbf{U}\Sigma\textbf{P}^{\mathsf{T}}\textbf{x}\right\|_{2} = \text{argmax}_{\textbf{x}\in S} \left\|\Sigma\textbf{P}^{\mathsf{T}}\textbf{x}\right\|_{2} .\end{align*}

I don't know whether I'm on the right track or how I should go on.

1

There are 1 best solutions below

0
On BEST ANSWER

One approach to take is as follows. If we make the substitution $\mathbf y = \Lambda^{-1/2} \mathbf V^T \mathbf x$, then we end up with the equivalent problem $$ \operatorname{argmax}_{\mathbf y \in S_0} \|\mathbf A \mathbf V \Lambda^{1/2}\mathbf y \|_2, \quad S_0 = \{\mathbf y \in \Bbb R^n : \mathbf y^\top\mathbf y = 1\}, $$ which is a standard optimization problem. The Rayleigh-Ritz theorem tells us that the solution is any unit-length eigenvector associated with the largest eigenvalue of the matrix $$ (\mathbf{AV}\Lambda^{1/2})^\top(\mathbf AV \Lambda^{1/2}) = \Lambda^{1/2} \mathbf {V^\top A^\top A V} \Lambda^{1/2}. $$