What is the optimal point in the nullspace of A using Lagrange multipliers?

[hoffmann]

Does anyone know how to approach this problem?

Let A be an m×n matrix of rank m, where m<n. Pick a point x in R^n, and let x∗ be the point in the nullspace of A closest to x. Write a formula for x∗ in terms of x and A.

What exactly is the significance of the point x* in the nullspace of A?

 

[hoffmann]

i think this question has something to do with the orthogonality of subspaces and is analogous to saying the shortest distance between a point and an axis is just a perpendicular line...

 

[pamparana]

>> What exactly is the significance of the point x* in the nullspace of A?

So, Ax* = 0 which is basically what it means by x* being in the nullspace of A. x* is a vector which multiplies A to take it to 0.

I think it has something to do with the least square solution for linear systems.

 

[pamparana]

I think you should think of the solution in terms of the projection of x onto the nullspace of A, which would be x*.

This is simply given by A*(A'A)-1*A'*x. Sorry, I am not fluent with latex.

A' = transpose of A.
-1 = inverse
* = multiplication

Refer to the Strang book on least square and projection of vectors onto the column space of a a matrix.

 

[Dafe]

We know that the row space is in $$R^{n}$$ and that it is orthogonal to the null space.

Imagine that we have a 2x3 matrix with rank 2. It's row space would be a plane in $$R^{3}$$, and it's null space a line perpendicular to that plane. If we pick a point $$x$$ in that plane, wouldn't the point closest to the null space be that same point x?

I'm eagerly awaiting someone to help us out :)

 

[hoffmann]

^^ i think you're on the right track, dafe.

i think an analogy to this problem is, what is the shortest distance between a point in the xy plane and the x axis. it's just a line perpendicular to the x-axis.

so in the context of the problem i asked, it's like...the dot product between the point x and...the row space? something like that...

 

[hoffmann]

ok, some help:

1) set this up with a variable (btw, better to call the starting point x0 rather than x, since it is fixed), an objective function and a set of equality constraints. Write them down. You should replace the objective function by something nicer: for example no square roots, since to apply Lagrange you need a differentiable function.
2) show geometrically in terms of the level sets of the objective function and the tangent space of the constraints that the vector x0 - x* is perpendicular to the null space.
3) form the Lagrangian. solve.