Monthly Archives: March 2006

paper a day : a counterexample for Gaussian feedback capacity

Posted on by

This is kind of a cop-out, since it’s a two-page “note” rather than a real paper, but since I’m so out of practice of reading and synthesizing papers I think that it’ll be a baby-step back into the swing of things. This paper is another information-theory one, but it uses a more general strategy that is easily explained to a general audience.

A Counterexample to Cover’s 2P Conjecture on Gaussian Feedback Capacity
Young-Han Kim
ArXiV : cs.IT/0511019

Imagine you have a communication channel that can be modeled as:

where X is the input, Y is the output, and Z is a stationary Gaussian process (not necessarily white noise, but possibly shaped with some spectrum). The approach information theory uses is to say that we’ll limit ourselves to a block of n time steps and then pick a set of 2nR sequences of length n that will encode 2nR messages. These sequences are called codewords and R is the rate of the code, measured in bits/time. If you use n = 10 time steps at rate R, you get a total of 10 R bits, which can stand for one of 210 R messages. A coding system for this model picks a set of codewords and a decoder that will take the noisy output Y = X + Z and guess which codeword was sent. Shannon’s Noisy Coding Theorem says that there’s an number C, called the capacity of the channel, such that for any rate R below C, the probabiliy of making a decoding error goes to 0 as the blocklength n goes to infinity.

Of course, you have constrained resources, and in the above Gaussian problem we assume that the power (squared Euclidean norm) of the codewords is constrained to n P. If we fix the noise power as well, the capacity is neatly parameterized in terms of P and we can denote it by C(P). The paper here is about the role of feedback — if the encoder knows exactly what the decoder receives, then picking codewords “in advance” may not be a good idea, since the encoder can adapt what it sends based on “how confused” the decoder is. There’s a longstanding conjecture that feedback can’t improve the actual capacity by more than doubling the effective power, so that CFB(P) is smaller than C(2P).

It turns out this is false, and the scheme used to show it is a modification of an old one by Schalkwijk and Kailath (Transactions on Information Theory, 1966). The intution is that with perfect feedback, the encoder knows exactly what the decoder does, and therefore can mimic the decoder’s operation perfectly. Imagine Alice is talking to Bob, but Alice knows exactly what Bob thinks she is saying. Using this knowledge, she can tailor the next thing she says to correct Bob’s misunderstanding as best she can. Bob will still not quite get it, but will be closer, so Alice can iteratively zoom on the precise meaning until she’s satisfied that Bob has gotten close enough.

Another way of thinking about it is helping someone hang a picture. You can see if the picture is level or not, and you issue commands: “two inches higher on the left,” “one inch on the right,” “half an inch on the left,” “a nudge more on the right,” until it’s hung straight. This is precisely the intuition behind the Schalkwijk-Kailath coding scheme. With this feedback you can get more precise than you could without, and similarly in this Gaussian communication example, you can communicate more bits reliably with feedback than without.

The result is not earth-shattering, since there’s another result that says you can get at most half a bit per unit time with feedback than without. But it’s a nice application of the coding scheme and a cool demonstration of the usefulness of concrete examples.

Advertisement

ivey-divey

Posted on by

I’m listening to Don Byron’s album Ivey-Divey, which I picked up from the SF Public Library earlier this week. I’m a bit of a Byron enthusiast, so I tend to view everything the man touches as gold. Part of this is from seeing him at Yoshi’s back when they had student tickets and let people stay from the 8pm set to the 10pm set if the latter hadn’t sold out (Yoshi’s has since become lame and student-unfriendly). Byron’s approach to albums is often that of a curator — works like Bug Music and The Music of Mickey Katz are examinations of eras or genres of music. The former is early Ellington, Raymond Scott, and John Kirby, and is a real delight. The latter is a jazzy klezmer variety act. Other albums take genres and deconstruct them a bit, like This is #6 or (arguably) Nu Blaxploitation. The album Romance With The Unseen is a little more straightahead but features a jaw droppingly beautiful version of the Beatles’ I’ll Follow The Sun with Bill Frisell on guitar.

Ivey-Divey takes a look at a recording session with Lester Young, Nat King Cole, and Buddy Rich. The bass-less combo has a charm and sound all its own (I’ve only heard the original once, but now it looks like I’ll have to buy it). Byron isn’t “doing Lester Young” on this album, however. He places those tunes next to some originals and classic Miles Davis. He has a killer combo — Jack DeJohnette on drums and the monstrously talented (and young) Jason Moran. Better players you couldn’t ask for, and when the chemistry is on and the soloists are quoting each other’s licks you know something’s happening.

It’s easy to complain that the album is stylistically disjointed. You have to remember that Byron is not only the best clarinet player alive, he’s one of those great curators who juxtaposes with intent. So you get a funky tune like “Leopold, Leopold” (you have to know your Bugs Bunny) followed by a Freddy Freeloader that starts out with just the clarinet, singing to itself before being joined by a Monk-like plunkety-plunk and light high-hat taps and slowly working itself into a lumber like Leopold and then flying off somewhere else with Moran’s hypnotic solo.

I can’t believe I didn’t listen to this album until know. What else have I missed out on?

college towns

Posted on by

I’m sitting with Amrys in an Espresso Royale in Madison. She’s reading a book before class and I’m trying to clean up a writeup on for my research. Espresso Royale was one of my favorite hangouts in high school, and I was distressed to learn, upon moving to Boston, that it was in fact a chain. But there’s something familiar about the place here beyond the Generic College Coffeehouse thing.

Maybe it’s the glassware or ther furniture, the branding of the place (which only became so coordinated and overt in the late 90’s, I think). It’s a manifestation of a greater sense of “home” that I get here. Maybe all midwest college towns are somehow the same. The snow is falling thick and wet outside, we’re warm in here with our coffees, and 90% of the people in here are working. It’s comforting like my recent sojourn in 1369, but this nostalgia runs farther back, to the days of my purple spiral notebook, Ritz crackers, and Coca-Cola.

Clapping Music

Posted on by

Via the Greenleaf Music blog, a link to a video of Steve Reich‘s piece, Clapping Music (go to Multimedia/video). It’s one of my favorite minimalist pieces, mainly because of its (kind-of) accessibility. It’s music and rhythm stripped bare, a piece you can perform anywhere as long as you have two people and functional hands (and perhaps a lack of pain receptors in those hands). It’s also great walking music.

death and taxes

Posted on by

Upon a preliminary inspection of my tax documents this year, I made myself a martini (Plymouth Gin, dry, up, with a twist of lime). My income from last year is tripartite (approximately) — fellowship, wages as a TA and RA, and self-employment as a singer. After reading a patronizing walkthrough of part of the tax code (“the artist temperament simply does not interface well with the exacting rule-filled world of federal and state taxation” — WTF?), I realized that the combination of more complicated income and saying goodbye to TurboTax for price-gouging has left me with no recourse but to slug it out mano-e-mano with the good old inimitable inimical 1040.

It seems that I must file a Schedule C with professional activity code 711510 “Independent artists, writers, & performers” and Schedule SE for self-employment. It warms the cockles to be called a “professional” and “independent artist” but the additional headache of schedules and forms (no doubt in triplicate) makes me expecto resurrectionem mortuorum et vitam venturi saeculi. Komm, suesser tod. Come, butler, come fill me a bowl of the best. And if you do bring me a bowl of the small, then the devil take butler, bowl and all!

9 parts of desire, part 2

Posted on by

Upon rereading, my review of 9 Parts of Desire may have been a little too positive. There are definitely problems with the play, especially in its relationship to its intended audience. I was initially impressed by what the play managed to do correctly and the versatility of the actress, but then the lacunae became more apparent.

Firstly, class is only tangentially dealt with in the play. Yes some of the 9 women are poor, but in Raffo’s scramble to give them strength and agency, she didn’t really address the relationship between them — which women enable the oppression of the others? What are the political forces that are relevant to them? It’s set up as a Baathist/Saddam versus American/Bush conflict, but that is a gross oversimplification, as the news points out. We’re given 9 snapshots of women but only the finest of threads stitching together their relationships to each other.

This is further complicated by the choice of these 9 snapshots. As I tried to argue with an acquaintance last night, someone will take issue with any finite number of images you take as “representative” of the spectrum of Iraqi women. Her complaint was that the choices were stereotypical — drunken expatriate, politically opportunistic artist, helpless 2nd generation immgrant. I think the more accurate criticism is that there weren’t very many complicated images, contradictions that couldn’t be fully explained by the text. To a degree, the women were textbook-logical. Even an irrationall impulse could be explained. It comes off a little pat, and thus non-representative.

Finally, there is the issue of catharsis. This play is playing in wealthy leftist Berkeley, and there is a real danger (and I’m sure it happened to many people) they they will go to see this play and feel like they have experienced the pain of these women and can now be cleansed of their guilt from complicity/ignorance/etc. I heard some paper called it an uplifting theatrical event, a feel-good play. It should have been more disturbing or challenging to avoid that. But you can’t control an audience’s reception that finely.

Was it worth seeing? I still think so. It’s standard practice to dislike all theater on some grounds, but my general feelings are positive, albeit shot through with some concerns. It’s too bad it closes today so nobody else gets to see it. But onward and upward, as they say.

9 parts of desire

Posted on by

I managed to catch this play at the Berkeley Rep last night. It’s a one-woman show by Heather Raffo, this time performed by Mozhan marn;ograve;. The play tells 9 Iraqi women’s stories, from an Iraqi-American obsessively watching the news for images of her extended family to a woman selling scavenged goods on the street, from an artist who painted Saddam’s portrait and is now asked to make a mosaic of Bush’s face on the floor of a hotel to the lone survivor of a bomb shelter that was mistakenly bombed by the Americans, vaporizing the bodies of those within.

The play’s most powerful device, used again and again without seeming old, is the simple statement of an atrocity. It is a kind of alienation that Brechtian manipulation can never accomplish. Hooda, an older expat living in London, is a pacifist who is for the war because Saddam ruined her country and “this war it was personal.” She tells us of her time in prison before fleeing Iraq. “They get to you by torturing those around you,” she tells us, and describes how a man was forced to listen to a tape of his wife being raped while their 3-month-old baby was placed in a bag with hungry cats. Layal, the artist, describes how her friend was taken by Uday, stripped naked, covered in honey, and fed to his dogs. This is what their lives are like, and in that matter-of-fact tone we are made to understand that we cannot possibly know what it is like to experience that.

The only moments that didn’t really work for me were at the end, where I felt like the sound levels were such that I couldn’t make out the text, and the moment where Layal smashes her supplies. In the latter, the transition is so abrupt that I couldn’t really make out why she snapped then. In the former, I was mostly disappointed because that is the moment in which everything is tied together before the denouement. All of the lines from the play come back through the tongue of Mulaya, the mourner. Nanna, the street seller, complains: “I have too much existence. Our history is finish.” Amal the Bedouin loves “with her heart, not with her eyes.” It’s a goldmine for drawing the piece together as a collective outcry against this existence, this injustice, and this horror that face these women, and it felt rushed and hard to decipher.

But no performance is perfect, and the positives in 9 Parts of Desire far outweigh the negatives. Marnò’s face is chameleonlike — she has a real gift for transformation, much like Sarah Jones. A program note that I read afterwards noted that the way in which a woman wears her abaya, her robe, tells us much about her class and her politics. It’s a simple signifier that allows the actress to physicalize her relationship to her politics, differentiate characters, and build a visual vocabulary, constrained by a single garment.

Unfortunately, the show closes this weekend (to make way for Culture Clash’s Zorro In Hell, which I am really excited about). But if it comes your way, definitely watch it. It changed my friend’s view of solo performance, and it may change yours.

charanga

Posted on by

Mission near 19th. This place is just a few doors down from Cha Cha Cha and serves small plates with a Cuban theme. They don’t have a liquor license, so there are no mojitos, but there is sangria, which is just fine. It’s hard to get a table here — the place is small and there’s usually a wait, but I’ve never found it to be ridiculous. It’s got that typical Mission blend of dressed down and pricey food, but the flavors here are more robust.

I said it’s small plates but it’s more accurate to call them medium plates. The price reflects the increased size. It was a while ago, so I don’t remember everything, but we did have a delicious garlic soup and a very tasty medium-rare steak (Niman Ranch, I think). As a warning, the shrimp are almost always cooked and served in the shell — while the former improves the flavor, or so I hear, the latter results in a big mess that invariably rubs off some of the flavor from the food. A good bed every time are the fried plantains (maduros) and the frijoles negros. That’s some tasty home-cookin’.

I’d recommend Charanga if you want to have light-to-medium dinner in a fun Mission spot. Of the similar places in the Mission, I’d have to say the food there has been the best, but I know people who would disagree.