I have a few vectors that are almost orthogonal (they are not all unit length). Measured in terms of their mean squared displacement, how can I find the smallest change that makes them exactly orthogonal?
I can arrive at an answer with Gram–Schmidt, but I'm not sure if it will be optimal.
On
Following the advice of kimchi lover, we may proceed by noting that the trace is they key to a useful matrix dot product, $$ \sum_{i,j} a_{ij} b_{ij} = \mathrm{Tr}\, A'B $$ Where $A'$ is the transpose of A. This operation has a nice geometrical interpretation: it is the sum of the dot products of each column in $A$ with each column in $B$.
If we would like to modify a matrix in a way that changes it as little as possible, we should minimize the magnitude of the difference between the old and new matrices. Using the above trace as the magnitude, we may write the expression that should be minimized: $$ \mathrm{Tr}\,(A-O)'(A-O) $$ Where $O$ is an orthogonal matrix and $A$ is the input matrix. We may simplify the trace to, $$ \mathrm{Tr}\,A'A + \mathrm{Tr}\,O'O -2\mathrm{Tr}\,AO' $$ Because $A$ is given and $O'O=I$, this minimization is equivalent to maximizing, $$ \mathrm{Tr}\, AO' $$ With the singular value decomposition $A=SDV'$, this leads to, $$ \mathrm{Tr}\,DV'O'S $$ From the matrix dot product identity above, it is clear that this is maximized when $V'O'S = I$, which implies that $$ O'=VS' \therefore O= SV' $$
Hint sequence: Consider the problem of finding the orthogonal matrix $U$ that maximizes $\text{tr} (DU)$, for given diagonal matrix $D$ with non-negative entries. And then consider the problem of maximizing $\text{tr}( AU)$ when $A$ is arbitrary. Finally, consider the problem of minimizing the trace of $(B-U)'(B-U)$ with respect to orthogonal $U$, for given matrix $B$.