Why minimise the norm? What’s the rationale? This video shows how you find the least norm solution for an underdetermined system., but why you would seek such an solution in the first place. ( in the type of problems i deal with, often there is a more ‘natural’ objective function)
an excellent question, and also extremely difficult to answer, not least because it is so general. Here are some thoughts! Apologies in advance for the stream of consciousness... If you have some more natural objective, you should of course use that. Perhaps most importantly when considering optimisation problems, you should be constantly thinking and questioning what you are optimising. And it sounds like you are which is great! Optimisation can be extremely dangerous - when you optimise with respect to something, you should expect performance to be bad with respect to everything else, since your optimiser will sacrifice all performance with respect to everything else for even just an epsilon improvement with respect to the criterion you choose. There is a nice quote: 'optimisation can expose the weaknesses in thinking which are usually compensated for by soundness of intuition' Ok tangent over - why minimum norm - or more specifically minimum 2-norm. Honestly, I think the main reason is that the problem captures a somewhat sensible notion of size, and admits an analytical solution. The big win is this second point. This is extremely rare - almost all other optimisations require a numerical solution. The reason that an analytical solution is so valuable is that it makes it much easier to understand how your solution depends on model parameters, how sensitive it is, how well numerically conditioned it is and so on. This allows you to build an intuition for going on, which is very important when trying to assess if your solution 'makes sense'. But why is a 2-norm natural? 2-norms of signals can often be associated with things like energy. Suppose for example the signal we are minimising the norm of corresponds to the velocity of an object. Then penalising 2-norm of the velocity corresponds to penalising the kinetic energy the object has over time (the k.e. in an object is typically proportional to the square of it's velocity), which may make sense if your objective is to keep that object still. But there are no rules here - 2-norms may not correspond to energy at all. But they will capture some notion of size, and when combined with the analytical nature of the solution to the problem, makes this problem a useful one to be aware of!
It would be nice if the title on the chalkboard was "Least Norm" instead of "Least Squares" since you really cover Least Norm, which is the dual of Least Squares but not Least Squares.
Sorry, I guess the naming is a bit confusing. Least squares problems are all about the equation y=Ax, and typically come in two different flavours. The first type - the type in this video, corresponds to the case that the equation y=Ax has lots of solutions. This happens when the A matrix is short and fat (i.e. the y vector has fewer entries than the x vector). The objective is then to pick the solution for which the norm of x is as small as possible. That's what I meant with least norm, but we could also say minimum norm. The second type of least squares problem corresponds to the case that A is tall and thin (now the y vector has more entries than the x vector). In this case the objective is to pick x so that we are as close as possible to solving the equation, and we do this by minimising the norm of (Ax-y). In fact, both these types of problem are special cases of what is called a constrained least squares problem (which is itself a special case of conic optimisation). Definitely worth reading up on or taking further courses if you're interested!
thanks so much for the explanation. but why do we design the objective function differently based on the size of matrix A (i.e. A matrix is short and fat or A is tall and thin) ? what's intuitive behind the objective?
