De Rerum Natura

I am co-writing a proposal to the National Science Foundation to apply ideas from compressed sensing to the problem of autonomously estimating mapping errors. This has got me thinking about this quote from Dave Donoho’s paper For Most Large Underdetermined Systems of Linear Equations, the minimal $l_1$-norm solution is also the sparsest solution.:

Many situations in science and technology call for solutions to undetermined systems of equations, i.e. systems of linear equations with fewer equations than unknowns. Examples in array signal processing, inverse problems, and genomic data analysis all come to mind. However,any sensible person working in such fields would have been taught to agree with the statement: “you have a system of linear equations with fewer equations than unknowns. There are infinitely many solutions.” And indeed, they would have been taught well. However, the intuition imbued by that teaching would be misleading.

On closer inspection, many of the applications ask for sparse solutions of such systems, i.e. solutions with few nonzero elements; the interpretation being that we are sure that ‘relatively few’ of the candidate sources, pixels, or genes are turned ‘on’, we just don’t know a priori which ones those are. Finding sparse solutions to such systems would better match the real underlying situation. It would also in many cases have important practical benefits, i.e. allowing us to install fewer antenna elements, make fewer measurements, store less data, or investigate fewer genes.

We have been taught to throw up our hands whenever a problem is labeled as undeterminate — it has fewer equations than unknowns. But this is too pessimistic. What indeterminacy really means is something more like an iron-clad guarantee. To say that a linear system $\mathrm{Ax}=y$ is undeterminate means that we cannot solve for a unique $x$ given any $y$. In other words, the null space of the linear operator $A$ has a non-zero dimension. But here is the crucial caveat that underlies compressed sensing as stated by Donoho above –most natural signals are sparse. We do not get to see all possible $y$ outputs. The space of all facial images is much smaller than the space of all possible images. This is precisely the point of manifold learning techniques in machine learning. So indeterminacy just means that we do not a 100% guarantee. But in a very practical sense, this does not matter when considering many natural signals. We can recover the input signal in spite of undeterminacy.

Examples of this phenomena are experienced by computer power users all the time. Text compression algorithms, which are lossless, cannot be a 100% percent successful. It can be proven that for some input string the compression will fail: the “compressed” text will be larger in size than the uncompressed one. However, when was the last time someone using gzip saw this happen? It does not happen because natural language text does not span the space of all possible character strings. A thousand monkeys pounding on keyboards produce mostly gibberish. This sparsity of natural language means that we can implement practical text compression algorithms that will compress text with an effective rate of 100%.

Right off Wolfgang Pauli Strasse in ETH Hoeggenberg, the 8th Optical 3-D Conference is taking place from July 9-12. I’m here to present the paper on autonomous DEM uncertainty estimates. The conference is meant to highlight the increased convergence between photogrammetry and related sciences in computer vision, robotics, data-handling algorithms, etc. But the conference is mostly attended by photogrammetrers (?) with a sprinkling of other scientists.

My talk has been pigeonholed into a “Shape and Surface” technical session which is incongruous, but there really is not any other better choice. A lot of the sessions are on how to characterize and improve the precision of camera or laser scanner systems. Since my talk is about going the other way (many bad measurements = few good ones, figure out errors on the fly instead of the lab), I wonder how it will be received.

As a graduate student in Physics back in the mid 1980s, I used to go two floors down from my office to a state mapping agency housed in Hasbrouck Hall at UMass. I mostly rummaged about looking at the expensive aerial images and maps. The guy in charge (I forgot his name) was very kind to me and occasionally pointed out good deals to me. I still have an aerial image of the Connecticut River crossing the Mount Holyoke and Mount Tom gap that I bought back then. I recently submitted my first mapping paper to the 8th Optical 3D Methods conference this July in Zurich. In retrospect, it looks to me like a long, random journey with an applied bias. The randomness was induced by the times I changed jobs and suspended in that uncertainty of the transition the bias of my interest made me think — “Maybe I can get a job making maps?”.

Dreams come true. Two years ago I was looking for a new job. I got a call from Brian Pinette asking if I was interested in a job doing a classifier for a Digital Elevation Model software system. I immediately said yes and that work has now lead to this paper on how to make DEMs better by exploiting the asymmetric matches computers make when asked to identify the same object in two photographs.