What vector x will maximize the norm of $\|Ax\|_2 / \|x\|_2$ (norm 2)

Question

I know for norm one vector $x$ should be a basis vector. Where one is in the column of matrix $A$.

and for infinity norm $x$ should have elements $-1$ for negative values of the maximum row and $+1$ for positive values of matrix $A$.

Now I am trying to figure out how can I maximize it for norm 2. I think it is related to the eigenvalues of (AT.A), however, I don't know where to start.

Answer 1

An (apparently) different approach using Lagrange multipliers:

To maximize $\|Ax\|^2=\sum_j\left(\sum_i a_{ij}x_i\right)^2$ subject to the constraint $\sum_jx_j^2=1$, one can introduce a Lagrange multiplier $\lambda$ and differentiate:

$$\frac{\partial}{\partial x_k}\sum_j\left(\sum_i a_{ij}x_i\right)^2=\lambda\frac{\partial}{\partial x_k}\sum_jx_j^2$$

$$\sum_ja_{kj}\sum_ia_{ij}x_i = \lambda x_k$$ which is the same as $A^TAx=\lambda x$. So $x$ needs to be an eigenvector of $A^TA$; since $\sum_j(\sum_ia_{ij}x_i)^2=\|Ax\|^2=\lambda^2\|x\|^2=\lambda^2$ we need to pick that eigenvector with largest eigenvalue.

Answer 2

You can restrict yourself to work with vectors $x$ with $\|x\|=1$. So you want to maximize $\|Ax\|$. And, for simplicitly, we may think of maximizing $\|Ax\|^2$. This is $$ \|Ax\|^2=\langle Ax,Ax\rangle=\langle A^TAx,x\rangle. $$ Because $A^TA$ is symmetric, it admits an orthonormal basis of eigenvectors, say $v_1,\ldots,v_n$ with $A^TAv_k=\mu_k^2v_k$ (I write the eigenvalues as squares because it is easy to check they are positive, and $\mu_1\geq\mu_2\geq\cdots\geq\mu_n$ are the singular values of $A$). Now $$ x=\sum_{k=1}^nx_k\,v_k. $$ Then \begin{align} \langle A^TAx,x\rangle&=\langle\sum_{k=1}^nx_k\,A^TAv_k,\sum_{j=1}^nx_j,v_j\rangle =\sum_{k,j=1}^n x_k\,\overline{x_j}\,\langle A^TAv_k,v_j\rangle \\ &=\sum_{k,j=1}^n x_k\,\overline{x_j}\,\langle \mu_k^2\,v_k,v_j\rangle=\sum_{k,j=1}^n x_k\,\overline{x_j}\,\mu_k^2\,\langle \,v_k,v_j\rangle\\ &=\sum_{k=1}^n |x_k|^2\,\mu_k^2. \end{align} Since $\sum_{k=1}^n |x_k|^2=1$, the above is a convex combination of $\mu_1^2\,\ldots,\mu_n^2$. So the sum will be maximum when $x_1=1$ and $x_2=\cdots=x_n=0$, and the maximum is $\mu_1^2$.

In summary, $$ \max\{\|Ax\|^2:\ \|x\|=1\}=\mu_1, $$ the greatest singular value of $A$ (or, what is the same, the square root of the greatest eigenvalue of $A^TA$). So the vector that achieves the maximum is a unit eigenvector for the eigenvalue $\mu_1$ of $A^TA$.