Minimizing L2 norm of a vector

Question

This will be more of a verbal question. What does finding the vector that minimizes L2 norm of that vector mean, logically? (which is bounded by another condition). Do I find the vector with numerically closest entries? This question is actually related to compressed sensing in image processing cost function definition. So if someone is familiar with cs theory it would be great as well. Thanks in advance!

Answer 1

Your interpretation seems okay - but I can try to add a few things.

From what I've seen in compressed sensing and image processing (especially in image restoration), usually you're looking for something like

$$\arg\min_x ||y-Ax||_2^2 + \lambda||Hx||_2^2,$$

where x is the new image you're trying to find, y is some measurement you have (typically an image that you're trying to denoise or maybe compress), and H is a high-pass filter (maybe a Laplacian filter or something).

The first term, which your question was initially about, tries to find an x that, after being transformed by A, is as close as possible to y. Clearly that first term would have a minimum when Ax = y, so it basically does just as you say. You can also think of this first term as the "energy of the reconstruction error". In other words, it is the energy of the error between the y that you have and the x that you're trying to approximate it with.

This second term tries to make sure that x isn't "too noisy". Instead of caring about how closely it matches y, it minimizes the high frequency energy (which in images typically corresponds to noise).

In other applications you might have something that isn't a high-pass filter, but the point is that you don't only care about the energy of the reconstruction error - this is not a good measure of how good x approximates y. By messing around with the scalar in front of the second term, you can control a trade-off between the two.

Here's a slideshow from my image processing class that talks about this - check out the first slide: http://www.eng.auburn.edu/~reevesj/Classes/ELEC7450/restricted/restoration_details.pdf. Note - the slide uses L where I use H, but they mean the same thing.