Author Archives: Anand Sarwate

paper a day : pseudodifferential operators for wireless communications

Posted on by

It should really be “paper every two weeks” or something — mostly it’s laziness in the blogging half of the reading a paper a day rather than the reading part. This one was pretty heavy going though.

Pseudodifferential operators and Banach algebras in mobile communications
Thomas Strohmer
Appl.Comp.Harm.Anal., to appear.

This paper is pretty heavy on the math but does a nice job of explaining the engineering concepts as well. There are two main thrusts here : modeling wirelss channels and OFDM pulse design. Multipath fading and Doppler shift in wireless communication channels can be mathematized via pseudodifferential operators, and designing OFDM pulses can be viewed as trying to make a certain matrix that represent the channel equalization sparse or concentrated on its diagonal. The tools Strohmer uses are pretty advanced (for me), but that’s because I’m not up on my harmonic analysis.

Wireless fading channels are typically modeled by a convolution with a time-varying filter. If the filter were time-invariant we could take Fourier transforms and write the channel as a multiplication by a transfer function. In the time-varying case we can make a similar representation in terms of a time-varying transfer function, which makes the channel law into a pseudodifferential operator whose Kohn-Nirenberg symbol is precisely the time-varying transfer function. Thus modeling constraints on the symbol can be translated into constraints on the operator.

The decay profile from multipath fading and the effect of Doppler shift provide constraints on the localization of the symbol in the time-frequency plane. The engineering constraints don’t give a nice characterization of the symbol per se, but we can embed the class of channels into a Banach algebra of operators with certein weight functions. We can also embed the symbol into a specific modulation space called a Sjöstrand class.

Turning to the equalization problem, OFDM pulses form a Gabor system, which is a kind of time-frequency basis for a function space. We would like to choose a basis so that recovering the data modulated on these pulses is easy. It turns out that the whole equalization operation can be written as a matrix that is related to the set of pulses, so the condition we want is for this matrix and its inverse to be nearly diagonal or sparse.

The big theorem (Theorem 4.1) in the paper essentially states that for pulses with good time-frequency localization, if the channel’s K-N symbol is invertible, then the inverse of the equalization matrix belongs to a certain algebra. This is the mathematical statement of the pulses being a “good system for communication.” This plus some more advanced relationship between different spaces gives a way of actually engineering a pulse design that can trade off the spectral efficiency versus inter-symbol and inter-channel interference.

All in all, this was a good paper to read but I don’t think I have the background to go and use these tools and techniques on anything because the math is pretty far above my head.

two thoughts for one so dear

Posted on by

sūryaṃ cakṣurgachatu vātamātmā dyāṃ ca gachapṛthivīṃ ca dharmaṇā |
apo vā gacha yadi tatra te hitamoṣadhīṣu prati tiṣṭhā śarīraiḥ ||
(Rg Veda X.16.3)

na jāyate mriyate vā kadācin
nāyaṃ bhūtvā bhavitā vā na bhūyaḥ |
ajo nityaḥ śāśvato ‘yam purāṇo
na hanyate hanyamāne śarīre ||
(Gita II.20)

paper a day : games people don’t play

Posted on by

Games People Don’t Play
Peter Winkler
Puzzlers’ Tribute, David Wolfe and Tom Rodgers, eds., A K Peters Ltd. (2001)

This is a short note on 4 little games that people don’t really play. Some are unfair, some are violent, but the interesting question arises for each — what is the best strategy for each player? I’ll describe two of them (with variants) — the other two are equally interesting, but there’s no point in repeating everything!

In “Larger Or Smaller”, Paula writes two numbers on different slips of paper. Victor picks one and has to guess if its the larger or smaller, winning $1 if he’s right. In one version the numbers are just different integers and in the other the numbers are drawn from a uniform distribution on [0,1] and Paula picks which one Victor sees.

Victor can do better than even (if only by a tiny amount) by adopting a clever threshholding strategy proposed by Cover. He guesses “larger” or “smaller” based on a comparison to his threshhold and will win slightly more than half the time (think about it). In the random version, the game is completely fair, with a simple strategy for Paula to choose which number to reveal.

In “Colored Hats” a dictator gives blue and red hats to a roomful of dissidents. They cannot communicate. Each can see the hats of the others and the simultaneously guess their own hat color. If they are wrong they are executed. How do we maximize the number of survivors? As a variant, the dissidents are lined up and guess from the back of the line to the front, so they can see all the hats ahead of them and hear the guesses from those behind them.

It turns out you can save floor(n/2) of the dissidents by having them pair up and guess their partner’s hat color. In the sequential version you can save all but 1 by having the first person guess based on the parity of the red hats in front of them. This provides enough bias for everyone to guess their own hat color.

This hat problem is particularly interesting because of its relation to some of the work in my Master’s thesis. So this paper is actually relevant (albeit tangentially) to my research. Plus it’s a fun and entertaining read. Recreational math and little games like this was what really got me interested in mathematics when I was younger. That and Raymond Smullyan, of course.

cosmopolitanism

Posted on by

Via Amardeep Singh, an article in the NY Times by Kwame Anthony Appiah on cosmopolitanism. His argument (and it’s a good one) is that movements to “preserve traditional culture” are misguided:

Talk of cultural imperialism “structuring the consciousnesses” of those in the periphery treats people like Sipho as blank slates on which global capitalism’s moving finger writes its message, leaving behind another cultural automaton as it moves on. It is deeply condescending. And it isn’t true.

He talks about the reception of soap operas in different cultures — because of their own local values and beliefs, a show like Dallas does not have the same meaning and interpretation to critics in the US as it does to viewers in other countries. It’s a nice complement to the reader-response theory I’m getting in the book I’m reading now. The essay is an excerpt from a forthcoming book, which I may just have to read.

Broiled shrimp with chanterelles and champagne reduction

Posted on by

This is a dish I made for the New Year’s Iron Chef : Battle Champagne party at my friend Usama’s swank pad. Champagne is used thrice in the recipe. The initial idea was given to me by Alexandra, and the fresh chanterelles were generously donated by Michael and Elizabeth (he picks them fresh in the Berkeley hills). Here’s what it looks like:
Broiled Shrimp with Chanterelle Champagne Cream

Marinade
1 cup champagne or cava
1/4 cup extra virgin olive oil
3 Ttbsp shallots
1/2 tsp fresh ground black pepper
2 lbs raw shrimp, deveined and peeled, leaving tails

  1. Mix marinade ingredients together with shrimp in a large plastic bag. If you’re like me and are bag-deficient, use a tupperware and toss the shrimp every once in a while to be fair. Let them marinate for around an hour.
  2. Take out the shrimp and skewer them (if grilling) or place them on a lightly oiled broiling pan (if broiling). Make sure the broiler rack is high. Discard the marinade and bag (it is tainted with disgusting shrimp cooties).
  3. Broil them for 2-4 minutes on each side until they look cooked/grilled. Let them cool and transfer to a serving dish or bowl.

Sauce
3 tbsp shallots
1.5 cups champagne or cava
5 tbsp champagne vinegar
1.5 cups heavy cream
1/2 lb fresh chanterelle or other fancy-pants mushrooms
1 tsp olive oil
1 tsp thyme (or more to taste)
2 tbsp honey (or less to taste)
salt and pepper

  1. Put shallot, champagne, and vinegar in a saucepan over medium heat util it boils and reduces to 1/2 to 2/3 of its original volume.
  2. In the meantime, chop the chanterelles roughly and sautee in olive oil until they give up some juice. Once they are cooked, take them off the heat.
  3. After the sauce reduces, add the heavy cream and return it to a boil until it reduces to about 3/4 of its original volume. Add the mushrooms, thyme, honey, salt, and pepper. Reduce it until it’s thick and creamy. You can add a little flour to thicken it up if things aren’t working quite right.

Serve the shrimp with the sauce on the side. Spoon a little onto the shrimp and munch away. Of course you can make any substitutions you like, especially to lower the fat content…

jai yun

Posted on by

I went to Jai Yun last night, and I have to say it was probably the best Chinese meal I’ve ever had. Unfortunately, I forgot to bring my camera and I missed a lot of the cold plates at the beginning since BART had problems and I had to run there. There are only a few tables in the place, and everyone’s dinner begins at the same time, because the chef has a fixed menu. The restaurant is prix fixe — you specify how much you’ll pay per head and they bring out dish after dish. It’s all small plates, so you get an amazing variety of food, all from around Shanghai. Afterwards the chef comes out of the kitchen and pretty much everyone applauds because the food was so damn good.

The most interesting thing about the meal was that most of the dishes were things I had never tried — abalone with eggs, this crazy grouper, tofu and celery, winter melon with ground pork, shrimp with ginko nuts, and so on. A few of the dishes were “familiar” from more American Chinese restaurants, but even these were wholly different in taste. The kung pao chicken was ridiculously spicy, but managed within that space to find a balance between the black and red pepper flavors. The orange beef thing was crispy thin slices of deep fried beef with a delicate orange flavor that just melted in your mouth.

All in all, it was a mouth-opening and wallet-emptying experience. Maybe I’ll go there again when I’m rich and famous.

medical exploitation of India

Posted on by

Via Krish, a story in Wired about how India is now the big site for clinical trials and drug development. Costs there are low, and as the editor of the American Journal of Bioethics noted:

Individuals who participate in Indian clinical trials usually won’t be educated. Offering $100 may be undue enticement; they may not even realize that they are being coerced.

I heard a radio program on this a few months back and tried to get my mother riled up about it, but it’s really just another strand in the rich and varied tapestry of India’s exploitation by the West/North/what-have-you.

As with most issues surrounding technology development, it boils down to an issue of pragmatics versus ethics. Pharmaceutical companies in Europe and Asia can’t find people willing to do clinical trials of their drugs in the US, even with some generous incentives. After all, who wants a placebo? On the other hand, you can get lots of volunteers for just $100 a pop in India plus paying the doctor to administer the trial, and the FDA will approve your trial. You get your drug approved, patent it, and prevent anyone in India from actually being able to afford it.

It’s not a problem specific to India either — patients in Russia are exploited in similar ways. When access to quality healthcare is limited, desperation is the primary motivating factor. Is it ethical to give a placebo in these situations? Should there be restrictions on how these studies are marketed to the public? Bioethics is going out the window in our rush for progress and refusal to shoulder the risks ourselves.