You are currently browsing the monthly archive for July 2008.

While trying to understand the Luby transform (LT) code, I stumbled upon the well known coupon collector’s problem. It took a while for me to figure out the connection, but as it turned out, there is a stronger connection between these two.  In LT parlance, if we were to use only degree one packets (that is, packets sent and collected as it is) what is the expected number of packets to be collected (when collected randomly, one at a time) such that all the required packets are collected atleast once. For illustration let us say we have $n$ information packets at the transmitter. The receiver collectes these one by one at random. How many packets on the average, we need to collect until we have collected all of the $n$ different information packets. Remember we are collecting the packets randomly (On the other hand, if we were to collect things deterministically, we just need to collect $n$ packets to get all these $n$, when done without replacement).

Assume that there are $n$ distinct coupon types.  We have, a large pool of these coupons at disposal. Every time you go to the shop you collect a coupon picked uniformly at random from the pool.  The picked coupon has equal probability of  being any of the $n$ types.  Naturally, some of the collected coupons (over multiple visits to the shop) may be of the same type. The question asked is this:  Suppose the coupon collector aims to have coupons of all types.  How many (number of visits) coupons he  has to collect till he possess all the $n$ distinct types of coupons?

In expectation, the coupon collector should make  $n \log(n) + O(1)$ visits to the shop in order to have atleast one copy of all $n$ distinct types of coupons . This coupon collector problem can sound a little confusing to a fresh reader. For simplicity sake we can assume that, there are $n$ differently coloured coupons at the shop. The question then is, on average (i.e., expectation) how many times one needs to visit (each visit fetch a coupon) the shop so that all coloured coupons are fetched atleast once.

There are $n$ different type of coupons.  The coupon collector collects a coupon upon each visit. The collected coupon is among the $n$ types, picked uniformly at random (from a set of possibly large pool of coupons) .  Since the coupon is drawn uniformly at random, there is a non zero probability that some of the collected coupons over multiple visits may be of the same type.  Suppose that at some stage, the coupon collector has $r$ different type of coupons collected.  The probability that his next visit fetch a new coupon type (not of the $r$ types he already have in the kitty) is $p_r=\frac{n-r}{n}$.  So, the expected number of coupons to be collected to fetch a new coupon type is $\frac{n}{n-r}$.  Let us denote this number by $E\left[N_r\right]$.

The expected value $E\left[N_i\right]=\frac{1}{p_i}=\frac{n}{n-i}$. From this we can compute the expected value of $N$. In other words, $E[N]$, the expected number of coupons to be collected (i.e, number of visits to the shop!) so that, the he would have all the different $n$ types of coupons is:

$E[N]=\displaystyle \sum_{i=1}^{n-1} {\frac{n}{n-i}}=n\sum_{i=1}^{n-1}{\frac{1}{i}}=nH(n)=n\log(n)+O(1)$

So, what is the trouble? This number $n\log(n)$ is prohibitively high a number to be acceptable (as decoding time of $n\log (n)$ is significantly higher than the wishful linear time $n$!). So, simply using degree $1$ is not a good idea. This is why Luby went ahead and identified some smarter distribution like Soliton (and its variants proposed later on, such as robust soliton and then the recent raptor codes by Amin).

Stumbled upon the news on New York times: it is about a new search engine being developed by some former Google folks. First there is excitement when it comes to a startup idea when you know that they know how it is to be confronting their former employers in business. Anyway, the new engine is called cuil (pronounced just like ‘cool’). I am all for new ideas. Hopefully we are into better search engines. Since these folks are also from Google, you can expect a certain Google standard guaranteed. Google undoubtedly changed the search engine business, by simply scaling the internet to a level hitherto unimagined. Yet again, a Stanford connection to a new startup. Tom Costello and his wife Anna Patterson (former Google architect) surely will know this business better than us (correction, better than me to say the least).

If their motto of producing a more appropriate search engine, bettering Google, then we should feel happy and proud of this adventure. Surely Google cant relax either. In all it is a win win for the world. A preliminary look at the search engine game me a good feel. I am not sure whether the change in appearance (after being stuck and used to Google search for so long) gives me this impression. Anyway I look forward to see their progress.

I leave it to you to try out for a comparison. I did a Cuil on “compressed sensing” and found this where as a google of “compressed sensing” displayed this. Google displayed the search result as a list (rows) where as the Cuil results to a tabular form. Too early to say anything discrete, but I am going to try the new one as well. Google is by far the fastest (at the moment).

Came across this New york times article on the Bhopal tragedy. It pains to know that the left over of that fateful tragedy still rolls on. Isn’t it still true that, the dreams of poor are never rich enough to be noticed? Their problems are not important enough to be cared?

I am quite saddened to hear about the demise of Professor Randy Pausch. The 47 year old CMU professor who was diagnosed with terminal cancer finally succumbed to death. It is unbelievable that, he showed courage to confront life when you know that there is nothing positive to look forward to. I have gone through his famous last lecture over and over and many a time wondered how can someone be so positive when the odds are so much against you to lean forward. Simply heroic. He showed us the value of life and the way to look forward to. I couldn’t agree more when he coined what “experience” mean,

Experience is what you get when you didn’t get what you wanted

Randy, may you rest in peace. Your life has changed many lives for good. You must be proud. You have truly left and enduring legacy. Our thoughts are with your family.

Randy Pausch giving the last lecture at CMU

His last lecture video is a must watch, if you have not done yet. Here is the video link:

Growing up in Kerala is an experience one cannot describe in few words. One must live through it to really feel it. It is different! This video

brings back a whole lot of those memories of childhood. I may be heavily biased here to say so much uniqueness about the social life in Kerala, but to me they simply remain so. The greeneries and the beautiful countryside, the many little ponds, rivers, streams, lakes, paddy fields, the list goes on. The days of Onam and Vishu are more than festivals for the people of Kerala. The expectations and excitement build around these festivals on children’s mind and the fun of playing so many little games: playing in rain, then invariably fall sick, all that in spite of being truly aware of the consequences. August-September time frame also had the monsoon settles when all the ponds and lakes are filled with water. As kids, those were special days to spend near full days swimming and play the various games by staying in water. Beautiful! Now, all those little games like Kuttikol, Pulikkali, lathi and the countless many games all must have disappeared and perhaps paved the ways for cricket or computer. I wish to believe that it is not!

Looking back, it is amazing that people of Kerala unanimously enjoyed the festivals like Onam, Vishu and Christmas irrespective of religious beliefs. The excitement of a festival was much more than religion, even though there is mythological trace to each of them.

Coming back to this video, it instantly took me to the days of Onam when we all kids (my siblings, cousins and neighbourhood friends) took pride in displaying new dresses, (more traditional it used to be) and group ourselves to play the whole day, with intermittent breaks for lunch feast etc and the pleasure of eating a sweet or two from the neighborhood house and to feel it tastier than the one at home.

And how can I have enough of those Kani konna pookkal (Cassia fistula), a seasonal flower seen all around during vishu summer days! (Courtesy, this beautiful image of kani konna is taken from http://www.ulujain.org/album/casino/casinoflowers/cassia1.jpg)

kanikonna poothappol

Until the recent past, south India was freed of all these callous folks who gets thrill by killing innocent people. Now, they are sneaking in and creating havoc everywhere. Inhuman activities happening anywhere hurts and the people who are affected only knows how bad they are. The sad trend is that, these are spreading across boundaries. Yesterday’s serial blasts in Bangalore is an example where the cancer is eating all sides of society. No matter who these stupid people/groups behind these and what their motives are, it is simple attrocious and pity to hear that such insane gangs exist. I fail to understand their doctrine of deriving sadistic pleassure by killing and terrorising common people who struggle to move a life on the side lane. Koramangala was a relatively quite area (but well, outskirts of them are heard to be a little notorious for the few religious gangs, but it was a hearsay I wished to not believe, but now truth must be properly investigated), but these inhuman activities are spreading everywhere.

To my innocence, I began to think that, there is support, directly or indirectly to these callousness. If the entire mass vehemently isolate the doctrine of killing innocent people these things simply cant continue. One random blast somewhere can be considered as the work of some streaky individual or group, but a series of such things ought to be coming from more planned inhuman groups. I really wish everyone think above these pity factions, whether it is religion or silly politics or any other doctrine. If you cant respect humanity and that too helpless armless poor people then your God cannot care you either.

While searching for the book Information theory, Coding theorems for discrete memoryless systems by Imre Csiszar and Janos Korner, I came across several sites which echoes the fact that this book is one of the rarest specimen on earth. However in the process, I found a blog forum which lists a whole lot of out of print books. This book, as expected is in demand already. We can even vote to request to bring the out of print books to a possible reprint. I am not sure how effective this is, but there is no harm in trying! We can suggest any books you may want to have a reprint. To me, this is a whole new and welcome idea. For learning, we should have access to the good books. Already quite a few demands (See this blog for instance) for the Csiszar and Korner book. Man, the world sometimes think alike!

Over the weekend, I finished reading a very nice book, The Kite runner, by Khaled Khosseini, an Afghan born novelist. This is first of his books, that I have read. In fact this is his first book as well. The book is written in an easy story telling style, but he did an amazing job to make me really satisfied. There were echoes of pain and suffering and the realization that the fate of a nation and its people can sometimes be so cruelly altered by invasion of other nations. Ofcourse that is a starting point. Later on the so called protectors of God then take over and make an even more mess where humanity is let to shame. Well, we can go on and debate those issues which unfortunately is affecting like cancer to human society as a whole, across the world.

Coming back to the book: The story The Kite runner is the story of two young boys Amir and Hassen. The setup is in Afghanistan, where these boys are born and spent their childhood. Amir was born in an affluent family, but his mother dies immediately after his birth. Ali, a servant to Amir’s father (baba) and his wife have a son named Hassan. On strikingly similar terms, after Hassen was born, his mother elope with someone, leaving him too motherless. The two kids are growing up together. Hassen lives in a hut in Amir’s mansion, baba’s house as he often refers to as. Baba (amir’s dad) loves both these boys, but Amir finds he being more critical to him than Hassan. Youn Amir thinks that baba’s attitude is perhaps due to the fact that Amir is indirectly responsible for his wifes (Amir’s mother) death (she dies after Amir’s birth). Baba’s friend Rahim Khan however is more lenient and friendly to Amir, and he provide support and encouragement to young Amir to develop interest in writing stories.

Amir and Hassen grows up together, with Amir as the lead boy and Hassen more submissive and obedient friend. The Russian invasion to Afghanistan then changes their life forever. Amir find himself as an immigrant in California, whereas Hassan forced to take a route to Pakistan. Fate shows the cruel flip to Hassen and he dies. Years later Amir take a difficult trip down east to rescue Hasan’s son, all in the middle of the Taliban reign. A tocuh of unrealistic melodrama where Amir fights with the brutal Talibans, but that afar the story is incredibly nice and touching to the reader. I have thoroughly enjoyed reading this.

In his blog Terence talks about a whole lot of things and I would very very highly recommend anyone, especially students and folks who are eager to learn just about anything. In one blog, he writes about the importance of writing down just about anything we learn, doest matter whether it is a simple thing you understood or a part of proof gathered. I have been following this method for a while and I found it amazingly useful as well. Well, I have decided to strictly enforce this on a more regular term.

Just aside, the beautiful thing about blogging in wordpress is its simplicity to incorporate mathematical expressions (Latex style editing is simple awesome). I have been searching for a simple way and here is the way. I am glad. Say for example this is $\int_{0}^{\infty} \frac{1}{\alpha+x} dx$ pretty. I am going to enjoy this:-)

I promise to write more about compressed sensing (and about several other things as I always) in future blogs. For now, this much is good enough for a first blog!

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 inter terminal communication. This is a problem of generating common randomness. This of course 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 focused well in the beginning to follow him, but partly because of the post lunch effect and partly because of the tiredness 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 Sanket etc (from the citation) and David Tse, L. Zheng, Al-Dahir and Shamai 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

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

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!

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!

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 couldn’t 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 game over 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.

Last winter Etienne Perron, Suhas Diggavi and myself together, 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 first version of the project discussing the background is available here in PDF form.

Xitip screenshot, the French version

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