How can the following equation be minimized over $x$?
$$f(x)=\|Axx^T-A\|_2^2$$
where $A$ is a $n\times n$ matrix of full rank and $x$ is an $n\times 1$ column vector. The norm is the Frobenius norm.
I tried to substitute $Ax$ but cannot find an appropriate solution. Can we somehow use the Cauchy Schwarz Inequality here?
We have that $\|B\|_2^2=\textrm{tr}\, B^*B=\sum s_j(B)^2$, where the $s_j$ are the singular values of $B$. You are interested in $\|A(1-cP)\|_2^2$; here, I write $P$ for the projection onto $L(x)$ and $c=\|x\|^2$.
As just observed, we can rewrite this as $$ \textrm{tr}\, (1-cP)A^*A(1-cP) = \textrm{tr}\, A^*A + (c^2-2c)\textrm{tr}\, PA^*AP . $$ Notice that $\textrm{tr}PC(1-P)=0$ because I can commute inside a trace. To minimize this, we first take $c$ so that $c^2-2c$ becomes minimal, so $c=1$. Then we must maximize $\textrm{tr}\, PA^*AP$. So we take $P$ as a projection onto an eigenvector of $A^*A$ belonging to the largest eigenvalue.
Your minimum equals $\sum_{j\ge 2} s_j(A)^2= \|A\|_2^2-s_1(A)^2 = \|A\|_2^2-\|A\|^2$. Here, $s_1(A)=\|A\|$ is the largest singular value, which equals the operator norm.