Wednesday, July 16, 2008

Lapidoth's talk: Matched filter done right

Today as part of EPFL annual research day, there were 3 interesting talks. In the morning Prakash Narayan gave a very interesting talk titled "Common randomness, multiuser secrecy and tree packing". Essentially it covered three distinct problems and he showed a connection among the three. The first problem setup is the following: A set of terminals observe separate but correlated signals. The classical Slepian and Wolf formulation of the data compression then is essentially the problem where a subset of the given terminals seeking to acquire the signals observed by all the terminals. And this is done by means of efficiently compressed interterminal communication. This is a problem of generating common randomness. This ofcourse does not involve any secrecy constraints. Now suppose a secret key generation problem. There the same subset of terminals seek to devise ``secret'' common randomness or a secret key through public communication. Assume here that an eavesdropper can observe this. So the setup is such that the key is concealed from the eavesdropper. Such a secret key can be used for subsequent encryption. Prakash's talk was then to explain the connection between the two problems. He went on to establish the connection to a problem in computer science namely the maximal packing og Steiner trees in an associated multi graph. I dont think I figured out the details that well, but it triggered some curiosity to read the work a little more detail. I hope to do that sometime soon.

The afternoon session had two talks. One was by Shamai who talked about Broadcast approach in communication systems. It went over time. I thought I focussed well in the beginning to follow him, but partly because of the post lunch effect and partly because of the tiredeness I lost the flow. From what I understood, he outlined a lot of communication scenarios incorporating the broadcast strategy. Some examples were MIMO rate diversity trade off, ARQ, multilayer schemes etc. A lot the work seems to have gone in this direction, especially Suhas and Sanked etc (from the citation) and David Tse, Zheng Al-Dahir and Shamey himself. I am somewhat amazed by the areas Shamai worked on. He seems to have covered a broad spectrum of research and yet produced some stellar work.

After Shamai, it was an interesting talk by Amos Lapidoth. He presented handsomely. I was attentive enough to follow this. Also, it happened to be a talk of different kind. He talked about the well known Matched filter used in communication. He sort of started with a little story. The story of a man from a village, venturing out of that place with a mission to find the meaning of life. So he goes to the mountains with a resolve not to come back until he finds the meaning of life. So days passed, months passed and years passed. Even after 10 years no sign of him. Finally he comes back after 11 years or so. The whole village feels curious: Aha he has come back. They ask him, wow, you have figured out the meaning of life. Please share us what is it? He says, with a pause: Life is (he pauses again).... : Villages out of patience ask him, : " You please go on .. life is ...". The man completes and says " Life is like a train!". Then they ask what you mean by "life is like a train". Then to the surprise of the entire village he says, "may be not!".

That was simply amazing a prelude for the talk. The talk abstract is the following:
One of the key results of Digital Communications can be paraphrased very roughly as follows: "in guessing which of two deterministic signals is being observed in white Gaussian noise, the inner products between the observed waveform and each of the signals form a sufficient statistic. Consequently, it is optimal to base one's decision on these two inner products." It is surprising that this basic result is never formulated as a theorem in any of the textbooks on the subject. This may be because of the difficulties in defining white Gaussian noise, in defining sufficient statistics for waveform observations, and in relating sufficiency to optimal detection. In this talk I shall describe a number of approaches to formulating the above statement as a theorem and point out some of their shortcomings. I will finally describe my proposed approach, formulate the theorem, and prove it from first principles. The proposed approach does not rely on the Ito Calculus, on Brownian Motion, or on generalized stochastic processes. It does not introduce non-physical infinite-power noise processes. Moreover, it is suitable for rigorously treating colored noise.

He gave a counter example where we can do better than matched filter. He says a Gaussian noise, but choose a point at random where the noise is made zero. Since it is randomly chosen (the null point) he claims it is still Gaussian. To me, that will result in SNR to blow up to infinity. So, are we missing something. I cant wait to read the full paper presentation of this. Otherwise, it seem to be a very very interesting way to look at matched filter, without needing the sojourn mathematical machinery.

Anyway all these talks are available (schedule at the moment) at [1]
[1]http://ic.epfl.ch/page65253-fr.html

Saturday, July 12, 2008

iFixit: iPhone-3G inside view

iFixit [1] did a rather fast job with providing an inside view [2] of the latest sensation iPhone-3G. They have done a superb job indeed. I was expecting Infineon to have a major presence in the 3G phone and to some extend Samsung as well, but this time it was the latter's SDRAM. You can read the details from [1]. I would rather strongly recommend you to! Here is the summary of the winners (number of chips listed after the maker):
Broadcom 1,Infineon 4,Intel 1,Linear Technology 1,Marvell 1,National Semiconductor 1,NXP 1,Samsung 1,Skyworks 1 (Man I wish this resurrect them),SST 1,ST Microelectronics1,Toshiba 1,Triquint 3 (Wow!),Wolfson 1.

Broadcom, Samsung and Infineon were expected. The surprise winners to me are Triquint and Skyworks. I wish this came earlier for Skyworks! If you look at Conexant at the moment (Skyworks spun off from Conexant earlier) it is pretty mazing how some leads turned up for them. Well, the market is quite demanding anyway. Ah, the surprise emission to me is CSR. I expected atleast for bluetooth they would have a winner there, but Marvell outwitted them with Bluetooth and WLAN!
Apparently, the pricing of this phone is pretty well done by Apple! Interestingly, there was huge rush even in Lausanne (Switzerland) where Swisscom had some offering day before yesterday.
[1]http://live.ifixit.com/
[2]http://www.eetimes.com/news/latest/showArticle.jhtml;jsessionid=PQBC4HQHI4MTSQSNDLSCKHA?articleID=208808554

Friday, July 11, 2008

Best of Man booker and the award goes to...

To me there was never a slim doubt on who this should go to. The one and only Salman Rushdie deservingly got this. Well, I am referring to the best of Booker award set up on the 40th anniversary of the Man booker prize. Hearing the announcement, this is what he said (in reply to a question),
"I really have no regrets about any of my work. This is, as I say, an honour not for any specific book but for a very long career in writing and I'm happy to see that recognized".
Let us also recollect that the same book (Midnight's Children), besides winning the Booker Prize in 1981 had also won the Booker of Bookers in 1993, which marked to honour the best Booker Prize winner in the first 25 years of the award. Now, this is still the best in 40 years. Pretty cool!

Aside, I am reading an interesting book now. A picked it from a friend's place last week and I found it a very very interesting read. The Afghan writer Khaled Hosseini, tells an amazing story. I am mid way through the book and I surely am going to write more about this later. As of now, I leave to remark that the book is about a young boy Amir born in an affluent family, who regrets in his later life for all the trouble he made to his trusted poor friend. I am thrilled by the story telling power of the writer. Simply superb (so far atleast). Interestingly, I saw a French translation of this book in one of the student house, a few weeks back. I am glad that, now I happily read the readable version!

Indian media: Too much of sensationalism

I don't get to watch Indian television daily, but I still keep an eye on them once in a while by visiting their websites. The two sites I visit so are CNN-IBN and NDTV. These are sort of the two large English visual media in India. For the last one month or so, one issue (other than perhaps the left Congress party fiasco over the proposed nuclear deal with the united states) widely flashed is a murder of a young teenage girl Arushi in Noida, a suburb of Delhi. The unfortunate girl apparently had to pay an innocent life to the cruel world of cunning and sheer callousness. The callousness of the cruel people leave the society to a state of shock and uneasiness. A sense of fear is invited all around. But my point is none of these.
I am appalled by the way the Indian media went about sensationalizing this news. I can understand the many soap Indian yellow news channels (most of the Hindi news channels are just that) going this way. The two celebrated Indian news channels NDTV and CNN-IBN are just no better. Day in and out their journalists competed to present a set of tabloid style news with the quest to attract the greedy readers and audience. I say this with utter disappointment. Here is a girl, the only child to their parents and she is lost. There is investigation on going. It is a basic courtesy not to write stories about the victim's family without having enough substance to what they talk about. News readers and media can talk senselessly on any topic and feel happy for it. Their flash news are spread across the country like tabloids. There must be some integrity and social responsibility before they venture into such silly acts. I dont have a problem when they expose any irregularities in the investigation or any cover up. But they should not air their verdict as if they are the supreme, even before doing a proper evidence collection. After saying nonstop incorrect stories about the family, now they can simply accuse the police and CBI for all what happened. Look at the family. They lost her daughter, they are portrayed as villain to the public, they lost their social reputation and health. Man this is agonizing. Police and CBI can be questioned, later on for all wrong doing. They can still be brought to justice, for any harm they created, but who can question or challenge the media? They offer all kind of accusations, but they are the one who enjoy the freedom to tarnish anyone of their choice. This is not a good going for the channels which claim to have reputed journalists. Pity!

Wimbledon final, you beauty!

Of late I have been so hard pressed for time that, my blogging has gone for a severe miss. Several things I wanted to write. The last 9 months or so, have been extremely tight to do anything to change it. But 2008 Wimbledon final:-I cant stop evading. It was one of the finest match I have ever seen, let alone in Wimbledon. Borg and McEnroe says this is the best final in Wimbledon and I couldnt disagree. How can I. When Nadal lost the last year edition, it was pretty close too. It was a case of no-one lost scenario. This year, however I have to say Nadal deserved it better. Federer, the champion we all know (and my favourite since Sampras) did what he is capable of: Making an amazing comeback to the verge of a turnaround. But the champion Nadal showed strength to beat Fedex in his comfort zone. One thing I am glad. Now there is some serious challenge for the championship. It never looked nice to have an easy gameover for the number one seed. I thought Fedex was not challenged enough over the years. This by no means is to diminish the class of my favourite player, but it appeals better when a champion comes out after stiff challenges. Sampras'e era to me that way was truly amazing. He fought against a series of champions, notably Agassi and Rafter (in grass mainly) and many others. He could never afford to relax against any of the seeded (even unseeded) players. Yet Sampras won 7 Wimbledon. Fedex was all set to achieve that number or may be even surpass, until recently. In the latest scenario, we have to wait and see how precious is to say that someone has won seven Wimbledon titles. This place an altitudes of sort to place Sampras among the pantheon of sports greats.

Coming back, to the Fedewx-Nadal final, I thought Fedex was not out of form at all. He served awesome and his backhand was as good as ever. Nadal served to Fedex body most of the time and he was aggressive from start as well. Because of the superior serve, Fedex always have this advantage on break points. If you look otherwise, Nadal owed more points and thus deservingly the champion. In the end, I am so glad to see the sort of respect they have for each other. Fedex humbly admitted and gave credits to Nadal, while Nadal was quick to praise Federer as the champion and as number one. Man, sporting spirit taken to a level. I am glad and happy that I follow this sport.

Aside, it has been a while I played tennis. The swiss summer is pretty nice, but my partner Adrian is away in Romania. May be I will get to play a bit in India during August-September. Exercise has been missing for a while. May be an hour of running around the lake side until Maladiere is a good idea. I need to plan my sleep and schedule to get that going. I hope I can do something about it soon starting next week.

Information theoretic Inequalities prover

Last winter along with my colleagues Etienne Perron and Professor Suhas Diggavi, we have developed a tool suit to prove inequalities in information theory. The tool is adapted from the previous work of Raymond Yeung and Ying-On Yan at Cornell. We have made it a complete C based software and removed the matlab dependency in the back end. There is also a pre-parser (using lex and yacc) built in to have flexibility on choosing random variable names. More importantly, a graphical front end is developed (using Gtk), which works well across the platform. Even though the beta version was ready in late 2007, for many reasons, including exhaustive testing (we always find scope for improvement) it was delayed. Last month, we finally made an official release. The original xitip project page in IPG has a short description and pointer to the exclusive Xitip page in EPFL (http://xitip.epfl.ch). A lot of things still need to be done, before we could say it is satisfactory. One of the main thing pending is the user guide and some kind of exemplified documentation. There is a technical report, I have prepared, but that is a bit too technical at the moment. Of course Raymond yeung's amazing papers introducing the theoretical idea behind this prover and his book are valuable resources. I have tried to provide a little more easy understanding of the concept using some illustration and toy examples. I hope to put this report anyway in the EPFL repository sometime.
The software is open source. If you are not bothered to compile and make an executable yourself, then please download the binary executable and just run. It is just a matter of double click in the latter case. We have Linux, Windows, Windows(Cygwin) and Mac versions available. There are two different linear programming software used. One is a Gnu open source GLPK and the other one is Qsopt (developed at Gatech). The Qsopt version is faster than the GLPK. Just in case you are obsessed with a perfect open source model, you could avail the GLPK [5] version.

Hopefully during this summer we will get to complete the pending work on this project. If any of you happen to find it interesting please don't forget to update us, on what you though about the software (Comments can be good, bad and ugly!).

Aside, I better mention this: Xitip is a software useful for proving (verifying) Information theoretic inequalities [7] only. Such inequalities contain expressions involving measures such as entropy, mutual information etc. It is a pretty handy tool if you are trying to prove some limiting bounds in information theory. In reality, there is broad classification of Shannon type and non-Shannon type inequalities. Non-Shannon type inequalities are not many, but they exist. Xitip at the moment is equipped to solve only the Shannon type inequalities. You can expect more information on this at the Xitip home page [2]

[1]http://ipg.epfl.ch/doku.php?id=en:research:xitip
[2]http://xitip.epfl.ch
[3]http://www2.isye.gatech.edu/~wcook/qsopt/
[4]http://user-www.ie.cuhk.edu.hk/~ITIP/
[5]http://www.gnu.org/software/glpk/
[6]http://en.wikipedia.org/wiki/Information_theory
[7]http://en.wikipedia.org/wiki/Inequalities_in_information_theory