Finding smallest vector satisfying an equation with a dot product

Question

I was wondering whether you could help me understand a solution to one of the problems from the 6.036 Introduction to Machine Learning from MIT Open Learning Library. The task is to find the smallest vector (with respect to the L2 norm) $\theta$ which satisfies the equation

$$\theta \cdot x = \frac{1}{y}$$

where $x$ is an arbitrary vector (with the same dimension as $\theta$), y is a constant taking either value $+1$ or $-1$ and $\cdot$ is the dot product.

The provided solution is:

$$\theta = \frac{x}{\| x \|^2} \times \frac{1}{y}$$

Even after looking at the solution, I am still not sure how this problem was supposed to be solved. It seems that the solution could be derived using manipulations similar to:

1. $\theta \times (x \cdot x) = x \times {1 \over y}$
2. $\theta \times \| x \| ^ 2 = x \times {1 \over y}$
3. $\theta = {x \over \| x \| ^ 2} \times {1 \over y}$

However, I struggle to see what could be the justification for transforming the original equation to the form in the first step, so I suspect this might not be the right way.

Answer 1

$ \theta \cdot x = | \theta | | x | \cos \psi = \dfrac{1}{y}$

where $\psi$ is the angle between the vector $x$ and the vector $\theta$.

Since $x$ and $y$ are fixed, this implies the minimum $| \theta |$ occurs when

$\cos \psi $ is maximum, and this occurs when $\psi = 0$ so that $\cos \psi = 1$.

And with this, $\theta$ will be aligned with $x$ , i.e. along $x$.

Thus $\theta = \alpha x$ , for a certain $\alpha \gt 0$ that we're about to find.

Plug this expression for $\theta$ in the original equation, you get,

$\theta \cdot x = \alpha x \cdot x = \dfrac{1}{y} $

Hence $\alpha = \dfrac{1}{x \cdot x } \times \dfrac{1}{y} $

Finally we note that $x \cdot x = | x |^2 $

This gives the answer mentioned in the lecture.

Answer 2

GeometryLover's solution is the way that I would solve the problem; it captures the geometric intuition behind the solution and can easily be made fully rigorous.

I want to point out, though, that it's also possible to brute-force the solution by solving the optimization problem exactly as stated, which might prove useful for other, less simple problem of similar flavor:

We are asked to solve

$$\min_{\theta} \|\theta\|^2 \quad \mathrm{s.t.}\quad \theta \cdot x = \frac{1}{y}.$$

This is a convex quadratic program whose unique solution can be found using the method of Lagrange multipliers: the constrained problem is equivalent to

$$\operatorname{ext}_{\theta,\lambda} \|\theta\|^2 - \lambda\left(\theta\cdot x - \frac{1}{y}\right)$$ whose optimality conditions are \begin{align*} 2\theta - \lambda x &= 0\\ \theta \cdot x - \frac{1}{y} &= 0. \end{align*} The first equations gives you $\theta = \lambda x/2$, and all we need to do is to find $\lambda$, which we can do by plugging into the second equation: $$\frac{\lambda \|x\|^2}{2} - \frac{1}{y} = 0$$ or $$\lambda = \frac{2}{y\|x\|^2}$$ which gives $$\theta = \frac{x}{y\|x\|^2}.$$

Answer 3

It may be useful to know that if $x$ is a fixed vector and $h$ is a constant, a plane in $n$-dimensional Euclidean space with an origin is defined by the set of position vectors $\theta$ that satisfy

$$ \theta \cdot x = h. $$

The plane defined in this way is perpendicular to the vector $x$ and is at the distance $\lvert h\rvert/\lVert x\rVert$ from the origin.

Given a point $P$ (in this case, given the origin) and a plane, the point on the given plane closest to the given point $P$ is at the base of the perpendicular line dropped from $P$ to the plane. In the case of the plane defined by $ \theta \cdot x = h, $ that perpendicular line is the line in the direction of $x.$

This tells us that the shortest $\theta$ lies along that same line, either exactly in the direction of $x$ or exactly opposite. That is, the solution is $\theta = r x$ for some scalar factor $r.$

With $h = 1/y$ and $y = \pm 1,$ you have $h = 1$ if $y=1$ and $h = -1$ if $y = -1.$ In either case $\lvert h\vert = 1,$ so the plane defined when $h = 1$ and the plane defined when $h = -1$ are the same distance from the origin. We therefore have two shortest vectors, one of length $1/\lVert x\rVert$ in the direction of $x$ and one of length $1/\lVert x\rVert$ in the direction exactly opposite to $x$.

Those two vectors are $$ \frac{1}{\lVert x\rVert^2} x $$ and $$ -\frac{1}{\lVert x\rVert^2} x, $$

which can also be written $$ \frac1y\left( \frac{x}{\lVert x\rVert^2} \right)$$ for $y = 1$ or $y = -1.$