Author Archives: Anand Sarwate

how JPEG works?

Posted on by

In this month’s Notices of the AMS, there was an article on how JPEG works [pdf]. These little articles are supposed to be about neat topics in mathematics or applications, and they are often uneven and sometimes contentious, as the Koblitz article [pdf] has recently demonstrated.

Even though I do signal processing research, I hadn’t looked under the hood of JPEG too carefully in any of my classes, so it was interesting to me to read about process of translating RGB to luminance and two chrominances, the DCT coefficient quantization scheme, and so on. The bit at the end on wavelets in JPEG-2000 I already knew about. But I think that for a mathematician the “why” was lost in all of the details of Huffman coding, Cohen-Daubechies wavelets, and so on. All of the engineering choices were made (in terribly contentious standards meetings, I’m sure) for a reason, and the choice of the mathematics is really a choice of model of “natural” images. He does a good explanation of luminance-chrominance vs. RGB in terms of the visual system, but what about the Fourier transform in terms of capturing edge detail in high frequency coefficients?

Unfortunately for me, the article ended up confirming my pessimistic view that standards look like a sequence of ad-hoc decisions. There’s lots of theory behind those implementations, and I think that might appeal to more mathematicians.

From graduate admissions to the future

Posted on by

I realize this is a bit rambling.

One thing that I’ve done for the last few years is act as an associate reviewer for graduate applications for our department. Basically this means I can chip in my 2 cents on applications during the initial review. I’ve already written about my shock at the kinds of letters people write (although I was certainly more naive then). One thing that I’ve come to realize over the years is that it is possible to write a full, good letter for someone whom you don’t know too well that both indicates the basis on which you can evaluate them (e.g. took your class and got an A, did research with your grad student, or did research with you) and is not ambiguous due to “conspicuous omission.” Writing a recommendation letter is an art — if you could just talk to the committee it would be a lot easier, but with N-hundred applicants of whom you admit at most 4 N, the written word is most of what they have to go on.

I often wonder about the total statistics of people who apply to graduate school, especially domestic students who apply to graduate school. At a state school like Berkeley there is a policy to encourage the admission of US citizens and permanent residents (a good thing, in my opinion). But how many of domestic students are interested in graduate programs? Are there many potential strong candidates who don’t even consider a career in graduate school? My gut feeling is that yes, there are many graduates who would benefit from and enjoy some exposure to engineering research at the graduate level who never even consider it. But that’s just a gut sense, which may be off.

The whole process raises a lot of big questions, ranging from “what is the purpose of the graduate program?” to “what can we do at the undergraduate level to bolster interest in postgraduate research?” to “where should the future of academic research in engineering go?” None of these has an answer, and I think that succinct answers are impossible unless you subscribe to some inflexible dogma. But they’re good to keep in the back of my head, I think, especially since I am (hopefully) looking towards a future in the academy.

Well, that’s done then.

Posted on by

Mystery Hunt 2008 is over.

This year I had to hunt from Berkeley due to thesis pressures by keeping in touch via AIM and Skype. Staying awake for a long time to work is much harder when nobody else is around to help keep the energy up. But sleeping 3 hours in your own bed is about four times as rejuvenating as sleeping 3 hours on a couch or floor.

Just one observation for now : infinitely ascending chains of cryptic crosswords with interchangeable clues are awesome. But try not to pay attention to them when they start talking to you.

Jonah Golberg is pantsed by Jon Stewart

Posted on by

Over the last few weeks I’ve been reading Sadly, No! document the atrocities of Jonah Goldberg’s new book Liberal Fascism : The Secret History of the American Left, From Mussolini to the Politics of Meaning. The book can be summarized by the following argument : Nazis liked organic food. Modern liberals like organic food. Therefore modern liberalism is rooted in fascism. Clever, eh?

Then I found out about this interview of Goldberg on the Daily Show. Wow.

See also this insightful contribution from Michael Bérubé on the line from Dinesh D’Souza (also one of my least favorite “commentators”) to Goldberg.

honorable mathematical intentions

Posted on by

In looking up a rather obscure paper on list decoding on Project Euclid I noticed that they link bibliography items to the MathSciNet reviews. I figured I’d take a look at the review of Shannon’s famous paper, A mathematical theory of communication. It turns out the review was written by Doob, and contains this little dig:

The discussion is suggestive throughout, rather than mathematical, and it is not always clear that the author’s mathematical intentions are honorable.

I have this image in my mind of Doob as the father of Mathematics, saying in a Southern accent “I’m not sure your intentions towards my daughter are entirely honorable, Mr. Shannon.”

a good excuse

Posted on by

Friends of mine returned from their honeymoon, during which they visited the Sossusvlei sand dunes in Namibia. They went as part of a tour group and there were two planes to take them back, except that one wouldn’t start. So first the pilot of the other plane tried whacking the engine with a hammer. Then they found that the solenoid had broken so they fixed that. Then they saw the battery was dead so they were stuck. The pilot announced that they would have to switch planes because “not enough things are working on this one.”

That strikes me as a good excuse to use for general things — it would all work out if enough things were working, but…

paper a day : Recovery of Time Encoded Bandlimited Signals

Posted on by

Perfect Recovery and Sensitivity Analysis of Time Encoded Bandlimited Signals
Aurel A. Lazar and László T. Tóth
IEEE Transactions on Circuits and Systems – I: Regular Papers, vol. 51, no. 10, October 2004

I heard about this paper from Prakash Narayan, who came to give a seminar at last semester, and I thought it was pretty interesting. In an undergrad signals and systems class we usually spend most of our time talking about converting an analog signal x(t) into a discrete-time signal x[n] by sampling x(t) regularly in time. That is, we set x[n] = x(nT) for some sampling interval T. There are at least two reasons for doing things this way: it’s simple to explain and the math is beautiful. If x(t) is a bandlimited signal, it’s Fourier transform has support only on the interval [-B,B], and the famous Nyquist–Shannon sampling theorem (which goes by many other names) tells us that if 1/T > 2 B the original signal x(t) is recoverable from the sequence x[n]. Since there is all of this beautiful Fourier theory around we can convolve things and show fun properties about linear time-invariant systems with the greatest of ease.

So far so good. But sampling is only half the story in Analog to Digital conversion. Not only should the times be discretized, but the values should also be discretized. In this case we need to use a quantizer on the samples x[n]. Fast, high precision quantizers are expensive, especially at low power. On the other hand, clocks are pretty cheap. The suggestion in this paper is to think about time-encoding mechanisms (TEMs), in which we encode a bandlimited x(t) into a sequence of times {tk}. Another way to think about it is as a signal z(t) taking values +b or -b and switching values at the times {tk}. The disadvantage of this representation is that linear operations on analog signals don’t turn into linear operations on the discrete signals. However, this conversion can be implemented with an adder, integrator, and a noninverting Schmitt trigger that detects when the output of the integrator passes a threshold.

TEM Figure

This paper shows that the circuit above can be implemented in real time and that {tk} are sufficient to reconstruct x(t). The recovery algorithm looks pretty simple — multiplication by a certain pseudoinverse matrix. The second part of the paper deals with the stability of the system with respect to errors in the decoder parameter or time quantization. The compare the scheme to irregular sampling algorithms. The tools they use for this analysis come from non-harmonic analysis, but the math isn’t all that rough.

This work is different than the sampling with a finite rate of innovation work of Vetterli, Marziliano, and Blu, which says (loosely) that regular sampling is good for a wider class of signals than bandlimited signals. It would be interesting to see if a TEM mechanism is good for those signals as well. That might be another robustness issue to explore.

Finally, one interesting connection (and possible another motivation for this work) is that neurons may be doing this kind of time encoding all the time. The integrate-and-fire model of a neuron is, from a black-box perspective, converting an input signal into a sequence of times, just like a TEM.

Choral Internet Radio?

Posted on by

Since I’ve all but abandoned choral singing this year in favor of writing my thesis (and boy does it bum me out), I’m at least trying to get more new old music in my ears. I tend to forget the iPod at home so I’ve turned to internet radio. For a while I was listening to KALX, but it’s not conducive to writing. For a while I was hooked on SomaFM, but no station there is quite what I want to listen to, ever. Then I turned to KKJZ in Long Beach for my jazz fix. I highly recommend it. Anuraag seems to be good for Indian classical music, but there must be other ones out there.

Now I’m itching for some good old vocal polyphony. Chant will do in a pinch. I came across this Choral Treasure station which is ok, but are there alternatives. Perhaps this is something Choralista should be able to tell me about, hmmmm?

[UPDATE: I can’t complain about any radio station that plays the whole Missa Papae Marcelli, so I hope I don’t sound like I’m dissatisfied with Choral Treasure…]