Compressed sensing is great for situations where capturing data is expensive (either in energy or time). It works by taking a smaller number of samples and using linear or convex programming to reconstruct the original reference signal away from the sensor.
However, in situations like image compression, given that the data is already on the computer -- does compressed sensing offer anything? For example, would it offer better data compression? Would it result in better image search?...
Since the whole point of compressed sensing is to avoid taking measurements, which, as you say, can be expensive to take, it should come as no surprise that the compression ratio will be worse than if the compression implementation is allowed to make all the measurements it wants, and cherry pick the ones that generates the best outcome.
As such, I very much doubt that an implementation utilizing compressed sensing for data already present (in effect, already having all the measurements), is going to produce better compression ratios than the optimal result.
Now, having said that, compressed sensing is also about picking a subset of the measurements that will reproduce a result that is similar to the original when decompressed, but might lack some of the detail, simply because you're picking that subset. As such, it might also be that you can indeed produce better compression ratios than the optimal result, at the expense of a bigger loss of detail. Whether this is better than, say, a jpeg compression algorithm where you simply throw out more of the coefficients, I don't know.
Also, if, say, an image compression implementation that utilizes compressed sensing can reduce the time it takes to compress the image from the raw bitmap data, that might give it some traction in scenarios where the time used is an expensive factor, but the detail level is not. For instance.
In essence, if you have to trade speed for quality of results, a compressed sensing implementation might be worth looking into. I have yet to see widespread usage of this though so something tells me it isn't going to be worth it, but I could be wrong.
I don't know why you bring up image search though, I don't see how the compression algorithm can help on image search, unless you will somehow use the compressed data to search for images. This will probably not do what you want, related to image search, as very often you search for images that contain certain visual patterns, but aren't 100% identical.
With regards to your question "...given that the data is already on the computer -- does compressed sensing offer anything? For example, would it offer better data compression? Would it result in better image search?..."
In general the answer to your question is no it would not offer better data compression at least initially! This is the case for images where nonlinear schemes like jpeg does better than compressed sensing by a constant of 4 to 5 and comes from the klog(N/K) constant found in diverse theoretical results in different papers.
I said initially because right now compressed sensing is mostly focused on the concept of sparsity but there is new work now coming up that tries to use additional information such as the fact that wavelets decomposition comes in clumps that could improve the compression. This work and others are likely to provide additional improvement with maybe the possibility of getting close to the nonlinear transform such as jpeg.
The other thing you have to keep in mind is that jpeg is the result of a focused effort of the whole industry and many years of research. So it really is difficult to do better than that but compressive sensing really provides some means of compression of other datasets without the need for the years of experience and manpower.
Finally, there is something immensely awe inspiring in the compression found in compressive sensing. It is universal, this means that right now you may "decode" image to a certain level of detail and then in ten years, using the same data you might actually "decode" a better image/dataset (this is with the caveat that the information was there in the first place) because your solvers will be better. You cannot do that with jpeg or jpeg2000 because the data that is compressed is intrinsically connected to the decoding scheme.
(disclosure: I write a small blog on compressed sensing)
One of the benefits of compressed sensing is that the sensed signal is not only compressed but it's encrypted as well. The only way a reference signal can be reconstructed from its sensed signal is to perform optimization (linear or convex programming) on a reference signal estimate when applied to the basis.
Does it offer better data compression? That's going to be application dependent. First, it will only work on sparse reference signals, meaning it's probably only applicable to image, audio, RF signal compression, and not applicable to general data compression. In some cases it may be possible to get a better compression ratio using compressed sensing than other approaches, and in other instances, that won't be the case. It dependes on the nature of the signal being sensed.
Would it result in better image search? I have little hesitation answering this "no". Since the sensed signal is both compressed and encrypted, there is virtually no way to reconstruct the reference signal from the sensed signal without the "key" (basis function). In those instances where the basis function is available, the reference signal still would need to be reconstructed to perform any sort of image processing / object identification / characterization or the like.