Let $A\in \mathcal{R}^{n\times d}$ be a matrix and its singular value decomposition be $A = U_A\Sigma_A V_A^T$. For any orthogonal matrix $U\in \mathcal{R}^{n\times l}$, let $U^\perp \in \mathcal{R}^{n\times (n-l)}$ be an orthogonal matrix whose column are orthonormal basis spanning the subspace of $\mathcal{R}^n$ that is orthogonal to $U$.

Then show that

$Z = \min_{x\in \mathcal{R}^d}\lvert\lvert Ax-b\rvert\rvert_2 = \lvert\lvert U^\perp_A U_A^{\perp^T}b\rvert\rvert_2$.

Note that this is the least square regression problem, and its exact solution is given by

$x^\star = A^+b = V_A\Sigma_A^{-1} U_A^Tb$.

Where $A^+$ is the Moore-Penrose pseudo inverse of $A$.

Reference this, Section 2.2.

  • 1
    $\begingroup$ What's your question ? $\endgroup$ – Gabriel Romon Oct 24 '17 at 19:52
  • $\begingroup$ To show that $Ax^\star-b = U_A^\perp U_A^{\perp^T}b$. $\endgroup$ – Sudipta Roy Oct 24 '17 at 20:06

Hint 1:

$min_x \|f(x)\|_2 \Leftrightarrow min_x \|f(x)\|_2^2$

Hint 2:

$\|x\|_2^2 = x^Tx$

Can you differentiate this and get the point $x$ where the expression is minimized?

%%% Fixed the answer according to the author's comments:

Let $ e = b - Ax^\star$

Then, $ e = b - AA^+b = (I-AA^+)b = (I-U\Sigma \Sigma^+ U^T)b = U(I-\Sigma\Sigma^+)U^Tb$

So, the matrix in the middle (which is like the Eigenvalue decomposition) has diagonal entries to be $0$ corresponding to those $u_i$ which are the basis vectors of rangespace of $A$, but $1$ for the ones which are the basis vectors for the orthocomplement of rangespace of A.

So, $e \in \mathit{R^\perp(A)}$

Also, from the last equality, since only the vectors that contribute to the orthocomplement survive the matrix multiplication, we will have $e = U_\perp U_\perp^T b$.

  • $\begingroup$ That would yield the normal equation. But how to use the $U_A^\perp$? $\endgroup$ – Sudipta Roy Oct 25 '17 at 7:02
  • $\begingroup$ Let $b^\perp = Ax^\star-b$. Then we know that $A^Tb^\perp=0$. Is is true that $b^\perp = U_A^\perp U_A^{\perp^T}b$? $\endgroup$ – Sudipta Roy Oct 25 '17 at 7:10
  • $\begingroup$ @SudiptaRoy Fixed. $\endgroup$ – learning Oct 25 '17 at 7:57
  • $\begingroup$ did not understand the last line. $\endgroup$ – Sudipta Roy Oct 25 '17 at 8:53
  • $\begingroup$ @SudiptaRoy Did you try matrix multiplication? $\endgroup$ – learning Oct 25 '17 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.