Skills

I lost myself browsing along videos at the Google Video and watched Ronaldinho's skillz: wow, wow (ad warning here) and the syper stylized wow.

Sunflowers

I drew spiral sunflowers (think i*a mod n for various i) this morning thinking of a problem that led me to formulate the following:

Given a partition of integers [0,n-1] into 2 lists A and B, check if for each i in A, for all j for which i+j mod n is in B, we have that i-j mod n is in A.

A subquadratic algorithm will be a start.

Across Countries

We speak about denied visas for a visiting scholar, or a student stranded elsewhere. We discuss the treatment of immigrants and trade barbs about countries. Some people feel righteous about their country, but mostly the accuser in one instance becomes the accused in the other.

But going away from scholars and students, the middle-class and rich, I want to talk about the ordinary people (think median household income of $43k in NY, think going on a school trip or vacation given as a gift) who want to travel, not emigrate. The travel across countries begins with a commute to the consulate. Taking a day off work to come to NYC and wait on the line.

- Medical insurance? But my provider does not cover travel. Do I have to pay extra $60 for the insurance?
- How much money do I need to have in the bank? I emailed them, they never replied to me.
- I changed my job, how am I going to ask my old boss for employment letter? I called the consulate, but nobody picked up the phone.
- The forms are on the web? Damn, I need to pay for another hour to get on that Internet in my neighborhood.

The whole process is predatory, no matter what country (India, Chile or Canada) is involved. People complain, "But there is no one to talk to. I want to explain my case." Instead they face a visa officer who speaks in direct, accusatory voice booming over the mic: "Have you any evidence of your planned stay?". People respond in a nervous voice, spill their bulgent (new word?) paperwork and dread the moment when the officer finds a blocking item on the "list", and alas, they have to return another day with more evidence. It is the trial before the travel.

Risk and Research

After a morning of coffee and scribbles at a cafe,
Symbols stare back speechless; I walk back home and blog instead.

A sparse approximation problem

Given an orthonormal basis of vectors B_1,...,B_n over n dimensions, k and n-dimensional vector V, the problem is to represent V using linear combination of at most k basis vectors. That is, find U=\sum_{i=1,..,k} a_i B_X_i, where each X_i is some B_j. Goal is to minimize ||V-U||^2 = \sum_i (V[i]-U[i])^2. Parseval's theorem implies that one can pick the k largest of | V DOT B_i |'s to minimize the error.

I have been interested in the problem of minimizing \sum_i W[i](V[i]-U[i])^2 for a given weight vector W. That is, the problem is to minimize weighted sum squared error where different dimensions have possibly different weights. It is a natural extension. Parseval's is not optimal anymore; it is acutally a long conversation to convince researchers that simple hacks like reducing the problem to \sqrt{W[i]}V[i] or (B_i DOT W) and applying Parseval's does not get optimal results (all such heuristics essentially end of solving the problem with a transform not in the original basis).

Problem: Design a polynomial time algorithm for any basis (even specific ones such as say Fourier) or prove its hardness. Known results: Special cases of Haar wavelets. Guha and Harb show that picking k largest with different scaling gives good approximations for other errors such as L_p and MAX_i ||V[i]-U[i]||, in SODA06.

Evangelizing: There is an applied algorithms perspective here that many miss. The reason a certain basis is used is because in a given application, most realistic signals are well represented by only a small number k of them and hence the basis is the most suitable for signals from that application. Therefore, it is really only sensible to ask the problem above when W has some of the properties of the basis vectors, and is not arbitrary. This eventually gets tricky to formalize. I tried an approach for the weighted problem and Haar basis in a paper, but this is far from what we need to know for other basis, and say for other error norms.

On being good

I am renovating my apartment and this entails dealing with contractors, suppliers and retailers; some are good, some not so good, and others remind one of Sergio Leone's il Buono, il brutto, il cattivo.

One of the good ones is Arnon Zadok, a master tile setter, an artist and the owner of Ceramica Arnon. He introduced me to gorgeous large (24X48 and larger!) tiles, supplied them promptly and also designed the tiling. See his work at Handmade Tiles volumes.

In Sergio's spectrum, where will General Grant fall? His tomb in Manhattan has beautiful mosaics by Pedro Silva. This is the piece of NY that reminds one of Barcelona. A little bit.

Referee-ing

We all know about Minimum Publishable Units (MPUs). I have seen papers where the authors seemed to have plodded along to just hit the MPU and then sprinted to write it up. Alas. But the papers I am reading these days seem to have MPDs: Minimum Publishable Deltas. The authors rummage around in dregs of prior work until they find the delta the previous authors have not done, and then sprint to write it up. Double Alas.

One response to MPDs is to apply blocking. One reads the paper from the beginning until the first place where one hits a good enough reason to feel indignant and then one sprints to write up a referee report that slays the paper (without reading the remainder). No, I am not recommending this response...

Coffee

We all know coffee is indispensable for proving theorems. Coffee was part of my life quite early (pre-10? pre-chicory in India?). Coffee was locally roasted, ground fresh and boiled with sugar and eventually some milk. I remember the bitter taste it left behind and liked playing with the sludge. Later, as a grownup, I read fictions that spoke of "mud coffee" in a noir-ish way and that was just fine with me, I liked playing with mud too.

Coffee is of course highly popular now worldwide. Check out ineedcoffee for recipes, cartoons, esoterica, and discussions. Fresh ground coffee is good, but fresh roasted coffee is better! Ozzie's at Brooklyn (friendly review, picture) roast their coffee if you care. Sometimes I do, and it is worth retasting the bitter taste from the past.

> Lemma is what you get with Decafs.
> Imagine, what if we had Coffee Embargo, like Oil Embargo? (Somewhat unrealistic, the producers are not so clustered?)

The Elements

It is difficult for me to watch Indian films. I don't mean just in terms of Bollywood or the Art films (of Bengal). I mean, it is difficult to watch them in, say Brooklyn, as I did this evening. They put me in a context, far away in time and space, and it is hard to deal with the flood of feelings. It is easy for me to put myself into alternative context to my everyday life while watching Kurosawa, not Ray. Anyway, I watched the movie "Water" (will "wind", "fire" and other elements follow?). It is a powerful movie about the widows of India, circa 1930's, set against the backdrop of Gandhi's rise to leadership and the independence of India. It is terrible how the redemption for the widow(s) is found not within their faith or their daily struggle, but in the sliver of hope and escape that Gandhi presents to them, to rest of the society and ultimately to the whole country. River Ganges and its banks are overpowering.

Transitions

I am in the middle of many transitions. On a train ride, I read what I found (long story) in my backpack. "I am History" by Mike Garey. Beautiful, short, David Mamet-like writing of Mike's time at Bell Labs, beginning to the end. David Johnson, Ron Graham, Ed Coffman, Peter Winkler and others appear and the writeup captures the excitement, mentoring and friendships found in Bell Labs of the past. Well, may be not all in the past. The people from there are now elsewhere and still evoke and inspire similar epherma (thanks to Graham Cormode for planting the word in my psyche all day yesterday), physical or otherwise. The second item I found in my backpack was Lamoisse's The Red Balloon, a pretty book with perfect form factor containing the story of a boy who finds a magical red balloon and of its perils and rides. Must read, after Mike's book, balances the moods. I went from nostalgic and reflective to playful. Shortly after that I was walking down 23rd street and three kids sauntering behind me and yelled out, " I like your hair, I like your beads, I like your walk and I like your shirt". I regreted not wearing stylish shoes, sigh.

A lemma

When I was a graduate student, I wanted to learn a lemma a day (may be I should have set my sights higher and targeted a theorem a day, sigh). Here is a cute lemma.

Consider f_1,f_2,..,f_n such that each f_i is non-negative and not all 0. If (\sum_i f_i) (\sum_i (i^2 f_i))= (\sum_i (i f_i))^2, then there exists a unique f_i not equal to 0.

Sumit Ganguly uses this claim and shows a proof in his paper on Counting distinct elements over update streams.

Trivia

I was invited to the Frontiers of Engineering meeting organized by the NAE recently. These meetings are often fun, with speakers discussing large swaths of impressive engg achievements. The nanotechnology talks were great, defining it as as technology that manipulated materials at 10-100nm size where the material had different properties (mechanical, quantum, whatever) from its "native" state. I liked the demos, eg., sheets with ceramic nanoparticle layers that can be applied to even convex walls of bathroom much like wallpaper. Also, the dinner talk by David Billington of Princeton Univ who spoke about major engineering achievements between 1870's and 1930's in US, was terrific. My favorite was his discussion about building the George Washington Bridge. Watch out for his book.

I quipped: are we going to have nano-managers? (nano-, micro-).

Btw, there is a collection of animals in New Brunswick that is a mini-(even micro-?) Zoo. It has Dolly the Llama. I am not kidding.