May 5, 2012

Beyond Shannon: infinity versus zero

Here is a recent paper on signal reconstruction:

Yamamoto, Y.; Nagahara, M.; Khargonekar, P.P.
Signal Reconstruction via  H-infinity Sampled-Data Control Theory—Beyond the Shannon Paradigm,
Signal Processing, IEEE Transactions on , vol.60, no.2, pp.613-625, Feb. 2012.
This paper presents a new method for signal reconstruction by leveraging sampled-data control theory. We formulate the signal reconstruction problem in terms of an analog performance optimization problem using a stable discrete-time filter. The proposed H performance criterion naturally takes inter-sample behavior into account, reflecting the energy distributions of the signal. We present methods for computing optimal solutions which are guaranteed to be stable and causal. Detailed comparisons to alternative methods are provided. We discuss some applications in sound and image reconstruction.

This paper proposes "beyond Shannon" signal reconstruction based on H norm. Recently, another "beyond Shannon" method, called compressed sensing (CS),  is widely studied in signal processing. It is interesting that in CS they use so-called 0-"norm," which is extremely-different from infinity norm.

Is there  a link between infinity and zero?

Related entries:
Zero, one, and infinity in compressed sensing

1. Massaki,

Congrats on starting a blog.

With regards to L_0 and L_infty, you might be interested in checking these out:

http://nuit-blanche.blogspot.com/2011/10/low-complexity-solver.html

http://nuit-blanche.blogspot.com/2011/10/compressive-sensing-literature-this_26.html

Cheers,

Igor.

1. Igor,

Thanks so much for a nice comment.
I think I could find a link between 0 and infinity norms in your blog entries.
I also remembered that L-1 is the dual vector space of L-infinity. This may be another link.

Best regards,
Masaaki

2. Yep, more connections indeed! There's also infinity norm appearing in the Dantzig selector. Dual formulations of the l-1 convex optimization problem also feature infinity norms. The duality comes from the relationship, if you have p-norm and q-norm, duality is when: 1/p + 1/q = 1 . put p= 1, 0 = 1/q, etc. I am also working on using the uniform norm in certain contexts in the application of sparse signal processing. I am working on the manuscript which is we hope to complete asap.

1. Mahesh,

Thanks for pointing that out.
Dantzig selector should be an interesting thing to consider the link.
I also hope your work is completed and published.

Best regards,

3. Congratulations on the paper and thanks for the new contributions therein, I really enjoyed reading it (recently appeared on my IEEE TSP RSS feed)! :)

1. Thanks so much!
IEEE TSP RSS feed is a nice tool.

4. The L-infinity norm is also seen in the Dantzig selector which can be used for reconstruction in compressed sensing: http://www-stat.stanford.edu/~candes/papers/DantzigSelector.pdf.
Here, the infinity norm is, however, used in the "fidelity constraint" measuring consistency with the compressed measurements rather than on the signal itself.

5. Thomas,

Thank you for the paper.
Yes, exactly. The infinity norm is used in the fidelity constraint in the Dantzig selector, which is different from the work Igor pointed out (see above).
That's yet another interesting thing!

Best regards

6. Are there pdf of paper available in arxiv or other open access?

7. Thank you for your comment.
You can find a pdf from:

http://www-ics.acs.i.kyoto-u.ac.jp/~nagahara/jst2_e.html