2
$\begingroup$

(a) Compute an orthonormal basis for $U$.

(b) Find $u\in U$ such that the Euclidean distance $||u-(1,2,3,4)||$ is as small as possible.

Here's what I have:

(a) To find an orthonormal basis, we'll use the Gram-Schmidt Algorithm. The process is as follows:

Given $k$ basis vectors $v_1,v_2,\cdots,v_k$, we apply the following steps:

  1. Let $q_1=\frac{1}{||v_1||}v_1$.
  2. For $i=2$ to $k$, repeat steps 3 and 4.
  3. Let $w_i=v_i-\langle q_1,v_i\rangle q_i-\langle q_2,v_i\rangle q_2-\cdots-\langle q_{i-1},v_i\rangle q_{i-1}$
  4. Let $q_i=\frac{1}{||w_i||}w_i$

The vectors $q_1,\cdots q_k$ are our orthonormal basis. Now, we apply these steps to the given problem. $$q_1=\frac{1}{||v_1||}v_1=\frac{1}{\sqrt{2}}v_1=(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0,0)$$ $$w_2=v_2-\langle q_1,v_2\rangle q_1=(1,1,1,1)-(\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{2}})(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0,0)=(0,0,1,1)$$ $$q_2=\frac{1}{\sqrt{2}}w_2=(0,0,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$$ So $\{q_1,q_2\}$ is an orthonormal basis for $U$.

(b) I recognize this as a least squares problem, but I'm a bit lost on how to actually set it up, because we don't have something with the form $Ax\approx b$. I mean, I know that $b=(1,2,3,4)$ and $u$ somehow represents $Ax$, but we don't have a matrix $A$, and $u$ is just an element of the span of $2$ vectors.

$\endgroup$
  • 1
    $\begingroup$ Hint: the underlying mechanism of the solution to the least-squares problem you’re familiar with is orthogonal projection onto a vector space. $\endgroup$ – amd Jan 7 '18 at 4:47
2
$\begingroup$

Your proof for part (a) is correct. For part (b) let $$ u=(\alpha , \alpha ,\beta ,\beta)$$ You need to minimize $$ (\alpha -1)^2+( \alpha -2)^2 + (\beta -3)^2+ (\beta-4)^2.$$ Partial derivatives are zero at $\alpha = 3/2$ and $\beta =7/2$. Thus $u=(3/2, 3/2, 7/2,7/2)$is the desired vector.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Do you think you could elaborate on this a bit? Is the choice that $u=(\alpha,\alpha,\beta,\beta)$ from the fact that the vectors that span $U$ have the same first two entries? $\endgroup$ – Atsina Jan 7 '18 at 5:06
  • $\begingroup$ Sure. From your part (a), you have found a basis in form of (1,1,0,0) and (0,0,11). $u=(\alpha,\alpha,\beta,\beta)=\alpha (1,1,0,0)+\beta (0,0,1,1)$ $\endgroup$ – Mohammad Riazi-Kermani Jan 7 '18 at 5:20
1
$\begingroup$

Because you have an orthonormal basis, things become increasingly easy.

The least squares problem is solved by

$$x_{ls} = (A^TA)^{-1}(A^Tb)$$

Where $A$ is a matrix which has your basis as columns and $b$ is $<1,2,3,4>$. Solve this for $x_{ls}$ and then the solution is $Ax_{ls}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is more along the lines of what I was searching for, but Mohammad's solution is slightly less computationally intensive. I wish I could accept multiple answers. $\endgroup$ – Atsina Jan 7 '18 at 6:02
  • $\begingroup$ @Atsina Because there is an orthonormal basis for the subspace, things are even easier than what been written here: $A^TA=I_2$, so your equation reduces to $x_{ls}=A^Tb$ and $u=AA^Tb=(u_1^Tb)u_1+(u_2^Tb)u_2$, i.e., it’s the sum of the orthogonal projections onto the basis vectors. $\endgroup$ – amd Jan 11 '18 at 1:10
1
$\begingroup$

The shortest distance to $U$ is measured along a direction orthogonal to it, therefore the element of $U$ that minimizes the distance to a given vector $b$ is the orthogonal projection of $b$ onto $U$, that is, the component of $b$ that lies in $U$.

There are various ways to compute this projection, but since you’ve already constructed an orthonormal basis for $U$, the easiest thing to do is to compute the individual projections onto the basis vectors and combine them. In fact, this is exactly what you do at each step of the Gram-Schmidt process: you compute the orthogonal projection of the current vector onto the space spanned by the orthonormal basis vectors generated up to that point and subtract that projection from the vector to get its component that doesn’t lie in that span. So, using that projection formula from the Gram-Schmidt process, $$\begin{align} u = (u_1^Tb)u_1+(u_2^Tb)u_2 &= \frac3{\sqrt2}\left(\frac1{\sqrt2},\frac1{\sqrt2},0,0\right)+\frac7{\sqrt2}\left(0,0,\frac1{\sqrt2},\frac1{\sqrt2}\right) \\ &= \left(\frac32,\frac32,\frac72,\frac72\right). \end{align}$$

The connection to finding a least-squares solution to the possibly-inconsistent linear system $Ax=b$ is that you essentially replace $b$ with its orthogonal projection onto the column space of $A$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Muhammad gave you a nice way using partial derivative so I'll just throw out here another way without using derivatives

The shortest distance to a plane create angle of $\pi/2$, so let's create the vector $\vec v=\begin{bmatrix}1-a\\2-a\\3-b\\4-b\end{bmatrix}$, this vector is the vector from the point $(1,2,3,4)$ to an arbitrary point on the plane.

I want that this arbitrary point on the plane will minimize $\vec v$, so I'll check when the vector create angle of $\pi/2$ to the plane($\langle\cdot,\cdot\rangle$ is the dot product):$$\langle\vec v,(1,1,0,0)\rangle=0\\\langle\vec v,(0,0,1,1)\rangle=0$$here I get 2 equations: $(1-a)1+(2-a)1=0\implies a=1.5$ and $(3-b)1+(4-b)1=0\implies b=3.5$ thus the answer is $u=(1.5,1.5,3.5,3.5)$

| cite | improve this answer | |
$\endgroup$

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.