Now that you've reminded me of Mackay's equally wonderful book, I can't decide which of these two is my favorite ;-) All math books should be like these two gems. I never get tired of reading them.
I know a guy who's using convex optimization as part of a project to sample an ultra-wide range of frequencies looking for a hidden narrowband signal (I leave it up to you to guess who would need that kind of device).
Apparently they use "compressive sampling" (http://en.wikipedia.org/wiki/Compressed_sensing) in conjunction with the convex optimization so they can avoid building the superfast A-to-D that you'd normally need to cover such a frequency range.
You can apparently prove that it'll always find the narrowband signal, as long as it's narrow enough.
It sounded like a broad-spectrum communications monitor.
If you want to know who's broadcasting anywhere in the range from 1MHz to 10GHz (example only -- I don't know the real range for this device), that's a bandwidth of 9.999 GHz.
You could scan freqencies sequentially, but it's slow and you might miss something. You can't afford to build a 20 GHz A-to-D converter, and even if you could, you don't want to build a computer big enough to process the resulting 80 GB/s data stream (assuming a 40 GHz sample rate with 16-bit samples).
The compressive sampling process is what allows you to sample at a lower rate (as long as you can assume that the signal you're looking for doesn't use too much of the total bandwidth). The convex optimization is apparently used to decide how to do the sampling in a way that's guaranteed to recover your signal.
The convex optimization is used to reconstruct the original signal.
The underlying compressive sensing theory says that if you do a measurement of a sparse signal, then convex optimization should allow you to recover that signal with high to overwhelming probability. The reason compressive sensing is interesting is that:
- the process of taking measurement is linear (no iteration a la JPEG), thereby allowing one to foresee very low powered sensors.
- the number of measurements is expected to be much smaller than what the Nyquist-Shannon theorem says (Nyquist is just a sufficient condition, not a necessary one), thereby realizing a de-facto compression of the signal with no a priori on the shape of that signal (except the knowledge that it is sparse)
- the measurements are automatically encrypted.
In the case of the broad-spectrum communications monitor, the message is known to be sparsely located all over the frequencies.
Thanks for the clarification, Igor -- my knowledge of this is second-hand, from a friend's description of an interesting project he's working on. I had never heard of compressive sampling or convex optimization before that, and it was eye-opening to see what's possible.
As it turns out, convex optimization is being seen by a few folks as the new least square. As wwalker mentioned, convex optimization is currently being used in solving for measurements taken with hardware implementing compressive sensing (or compressed sensing or compressive sampling). The A/D converter is just one of the application of compressive sensing. One of the most well known example is that of the single pixel camera at rice but there are many others. I have listed most of the known hardware implementing compressive sensing here:
One should note that while convex optimization has given some real impetus to the field (by providing theoretical bounds), signal reconstruction is also using speedier techniques nowadays even though linear programming techniques remains some sort of gold standard. For those of you interested in the subject, I write a small blog on the subject of CS:
convex optimization covers a lot of different problem types. in general, you are trying to minimize (or maximize) some function (the objective function) over a set of variables subject to a set of constraints on those variables. 'convex optimization' deals specifically with optimization problems where the objective function is... convex. this essentially means you can efficiently find the global minimum (or maximum if the function is concave)
ok, so a simple example: lets say you're on a hacker's budget and you want to maximize your caloric intake given your limited funds. This is your objective function. BUT, if you're like me, you can't live on ramen and mountain dew... i have a basic set of nutritional requirements. These are your constraints. For example, sodium has to be less than A and protein greater than B and so on and so forth. So you are essentially optimizing over ALL possible diets.
My guess is you'd end getting back: kale, potatoes and beans. Now that's a real hacker's diet!
At my day job, we use linear programming to calculate virtual capacities on airplanes, i.e. overbooking. There's a few other optimization techniques involved, such as dynamic progamming, but if you've ever been asked to take a different plane, chances are an LP was involved.
Those of you who may be interested in convex optimization may want to take a look at these "MIT OCW-like" pages:
http://see.stanford.edu/SEE/courseinfo.aspx?coll=2db7ced4-39... http://see.stanford.edu/SEE/courseinfo.aspx?coll=523bbab2-dc...
and those who are interested in convex optimization and Python programming, might want to take a look at these:
http://abel.ee.ucla.edu/cvxopt http://cvxmod.net