About a month ago, the National Science Foundationannounced new funding opportunities. Proposals for these grants are due in the Fall of this year. The program has three tiers of funding: small, medium, and large.
Proposal Window
Amount ($ M)
Duration (years)
Small
12/1 – 12/17
up to 0.5
up to 3
Medium
9/1 – 9/15
0.5 – 1.2
up to 4
Large
11/1 – 11/28
1.2 – 3
up to 5
There is no limit on the number of principal investigators that a funded project can have, but a PI may only submit two proposals.
address data of unprecedented scale, complexity, and rate of acquisition.
[Projects may support] processing needs for data from disparate and uncoordinated sources
demonstrate effectiveness in dimensions such as quality, scalability, accountability, interactivity, social responsibility, or resiliency to incomplete, uncertain, inconsistent, contaminated, or manipulated data.
should advance contemporary applications of societal importance
So say you want to use compressive sensing to lower the sampling rate of your measurement system. You first need to measure it in a basis which is sparse. You do this so you can sample it randomly far below Nyquist and save power in the process. However, what if the signal you are trying to measure is sparse in time? Then you’re in a little bit of a pickle, because you can’t sample this signal randomly without potentially losing information.
What I learned last week is that to compressively sense signals that are sparse in time, you need to first transform them into a domain that is not sparse in time and then sample randomly. One way to do this is to use the Hadamard transform to convert your signal of interest which is sparse in the time domain into a signal that is sparse in the frequency domain without any loss of information. The Hadamard transform is like taking a bunch of little DFT’s on your signal and putting them into a matrix.
However, if your signal is sparse in time, you probably still care exactly when your signal did the thing that is of interest to you, when it did whatever it was that you couldn’t afford to miss by sampling randomly. The latency or the group delay of your compressive sensing of a sparse in time signal is, ostensibly, going to be a pretty important piece of information to you. Unfortunately, I cannot find one paper that addresses latency or group delay in compressive sensing. To be sure, this has got to be incredibly difficult, if not impossible to predict. I would think that the iterative nature of the recovery algorithm alone (even though the order of its computational complexity can be assessed) must be very difficult to quantify in terms of time or samples.
Don’t worry, it’s just the fundamentals I don’t get; but it’s not for lack of traffic on the subject. There are some great resources on the internet about compressive sensing — which is a groundbreaking technique for reconstructing seemingly lost signals. Igor Carron has a great up-to-the-minute blog, Nuit Blanche on the latest news on compressive sensing and Rich Baranuik has a treasure trove of papers on the subject at http://dsp.rice.edu/cs. NPR did a story on compressive sensing that provides a good illustration of compressive sensing in practice. They have an example of an undersampled piece of music reconstructed using compressive sensing techniques.
Human ears usually pick up frequencies under 16 kHz, some as high as 20 kHz. Most speech is easily recognizable with only the frequency components at or below 4 kHz (for phone calls, speech is usually sampled at 8 kHz). CD’s are sampled at a rate of 44 kHz. In the demonstration on NPR, a musical track is sampled at a rate on the order of 100′s of Hz.
Hit Play on the control above to hear the undersampled version (sampled at ~100′s of Hz).
By using some fancy math, Jordan Ellenberg, from the University of Wisconsin, is able to faithfully reconstruct the original recording.
Hit Play on the control above to hear the sample reconstructed.
Compressive sensing has a wide range of possible applications. In general, there are usually three cases where compressive sensing is appropriate to use in a sampled system.
When the data is soon compressed after sampling
When the data is soon encoded for transmission
When the data is sparse
As it turns out, compressive sensing relies on some fairly complicated matrix algebra to work. Below are some of the topics I’ve encountered while reading about compressive sensing to try to figure out how it works.
Sparsity
A matrix is considered sparse if it can be represented with a much smaller set of values than its full size without much loss of information. For instance, take the matrix [1.0, 0.01, 0.01, 0.01, 0.01] and envision a scenario where it is treated, for all intents and purposes as [1.0, 0.0, 0.0, 0.0, 0.0]. If that representation is good enough for whatever calculation is performed on it, then the matrix is sparse. Say you wanted to know roughly what the average value of that matrix is. You could say it’s about 0.2 (as opposed to 0.208, which would be more accurate). The advantage is a far faster calculation: 1.0 / 5, instead of (1.0 + 0.1 + 0.1 + 0.1 + 0.1) / 5.
L1 Norm Minimization
L1 norm minimization is the technique the receiver employs to reconstruct the compressively sensed signal. The Wired article on compressive sensing gives a great overview of L1 minimization. In the example in the article, the L1 minimization algorithm creates a high resolution image from a low resolution one. It does this by
filling in shapes of color based on nearby known pixels. It iteratively follows this procedure, using smaller and smaller shapes until the picture is complete.
The L1 norm is a measure of distance in a 2-dimensional Cartesian coordinate system that gives the distance between two points. However, this distance is calculated as the sum of absolute difference of the coordinates of the two points. This is also known as taxicab geometry. It assumes that the only way to travel from one point to the other is in a gridded, rectilinear fashion, like streets in a major metropolitan area.
But how does L1 minimization preform this magic? I don’t know. This feat, I guess, is usually executed on a host CPU because when performace metrics are given for a new approach to L1 norm minimization, they are given with the qualification of what kind of machine was used. What’s more, this particular bit of matrix math, the part that actually recovers the desired signal, is iteratively executed. This means there’s really no telling how long this will take, which seems to make compressive sensing inappropriate for real-time sensing applications that rely on low-latency, such as feedback control loops.
Restricted Isometry Property
Isometry is a distance-preserving map between metric spaces.
characterizes matrices which are nearly orthonormal, at least when operating on sparse vectors. … There are no known large matrices with bounded restricted isometry constants, but many random matrices have been shown shown to remain bounded. The current smallest upper bounds for any large rectangular matrices are for those of Gaussian matrices
and further it defines RIP as….
Let A be an m × p matrix and let s < p be an integer. Suppose that there exists a constant δs such that, for every m × s submatrix As of A and for every vector y,
Then, the matrix A is said to satisfy the s-restricted isometry property with restricted isometry constant δs.
This really just completely confuses me. I guess the restricted isometry constant bounds the distance preserving transform between the two spaces? I have no idea, I guess I need to learn some more matrix math…
Coherence
Compressive sensing depends on mutual coherence, which is a matrix of the cross-correlations. But between what and what? I don’t really know, but I think it’s between acquired samples. That is, one sample and the next sample should have low coherence, so that they appear to be random and random measurements can be used for signals sparse in any basis.
I’m sure there’s plenty more I don’t understand, but that’s all I have for now.
Consider the single-order low-pass digital filter with constant a1. It has a pole at -1/a1. Now consider putting it in a feedback loop. The overall transfer function of the resultant system has a pole and a zero and acts as a highpass filter. Now consider repeating this infinitely: at each step taking the resultant transfer function and placing it in a feedback loop. I call this recursive feedback loops.
No matter how many times you perform this recursion on a first order lowpass filter, it can only yield another first order system with at most one pole and one zero. What’s more, in the limit, both the pole and the zero are at -1/a1 * φ, where φ is the Golden Ratio. The following proof shows it.
A Basic First Order System
The block diagram for a generic single-order lowpass digital filter is given in the block diagram below.
The output, y, is delayed by one sample period and then multiplied by a1 and subtracted from the input, x. It can be described by the following difference equation.
Taking the Z-transform of this difference equation and rearranging terms gives the following transfer function, H0(z).
A feedback loop in general can have the following form,
Which has the transfer function,
So the first-order system is like a feedback loop with H(z) = a1*z-1.
Now what if we had a feedback loop inside a feedback loop? How does a system of feedback loops in recursion behave?
Feedback Loops in Recursion
So to have a feedback loop in recursion, we need to replace the H(z) in the picture above with the picture above itself. This would mean that the y[n] signal, the output would be on the left and the x[n] signal, the input would be on the right within that block. An illustration makes it easier to imagine.
Where H0(z) is the transfer function of the first order system given in the previous section.
To help figure out the transfer function for this equation, I’ve labelled an intermediate node, w[n]. The next two equations can be found by inspection from the figure above.
Where w[n-1] indicates the previous value of the signal w[n] because it has been delayed by one sample by the z-1 unit delay element. Taking the z-transform of each of those equations and substituting for W(z) gives,
And reducing algebraicly to find the transfer function, H1(z), yields,
Notice that
which fits the transfer function for a feedback loop with H0 in the feedback path.
In the Limit
So what does this system look like in the limit, that is, if you keep nesting a feedback loop within a feedback loop with a first-order lowpass system at the lowest level of it, does this converge to anything?
Recursion Level
Transfer Function
Poles & Zeros
0
No zero pole = -1/a1
1
zero = -1/a1 pole = -2/a1
2
zero = -2/a1 pole = -3/(2*a1)
3
zero = -3/(2*a1) pole = -5/(3*a1)
By looking at the first few levels of recursion a few interesting things are already apparent.
None of them has more than one pole or one zero
The pole and zero each seem to be converging for increasing recursion
Notice the following pattern in the poles: {1, 2, 3/2, 5/3, …} * (-1/a1). In fact if we carry this through the first 30 levels of recursion, we see that it starts to settle on approximately 1.6.
This seems to be tantalizingly close to the Golden Ratio, but does that make sense? Apparently it does.
The transfer function of nested feedback loops is,
which looks a lot like the nested continued fraction for the Golden Ratio, but with the first-order transfer function at the end of it.
Notice the numerators and denominators in the poles in the table above are all Fibonnacci numbers. Our sequence of poles can be rewritten as
here pi is the pole for the transfer function resulting from the i-th level of recursion. In the limit, this becomes,
So the pole of the first-order system in recursive feedback is the original pole times the Golden Ratio. Even though the pole and the zero are separated by a level of recursion, that is the pole for one level is the zero for the next, in the limit, as the level of recursion increases without bound, they both go to the Golden Ratio divided by the a1 gain term (times -1).
I made a table of US Senators who tweet and how much. I’ve seen other lists of tweeting Senators, but most of them are unreliable. They usually contain usernames that have been compromised or don’t have any tweets associated with them. The usernames in this table came from the Congress in your Pocket iPhone app and do not include Senators with protected accounts.
The columns are sortable and contain the number of tweets made by that senator, the number of twitter followers that Senator has and the number of twitter users that Senator is following. The last column indicates whether or not the account for that Senator is a Twitter verified account.
The numbers are valid as of the date of this post. Unfortunately, as I said, it is a static list.
The table shows some interesting results. Claire McCaskill is the most prolific tweeting senator with 1377 tweets. Richard Shelby and Debbie Stabenow are tied for least tweets with 5. As expected, John McCain has far and away the most followers with over 1.7 M. The retiring Evan Bayh has the fewest followers, 96. Jim DeMint follows the most users, over 14k, while Ben Nelson and Debbie Stabenow don’t follow anyone. I guess Debbie Stabenow isn’t really engaged with twitter.
The only three twitter verified accounts are John McCain’s, Richard Lugar’s and Kirsten Gillibrand’s.
Demand Question Time is a movement dedicated to making permanent the question and answer period President Obama had with House Republicans a few weeks ago. Please sign their petition to make this useful bipartisan discussion part of our political infrastructure.
An update on the fundraising reported by the Capuano, Khazei, and Coakley campaigns comes form kennedyseat.com. The second reporting period ended on Friday. Below is a table tracking the first and second reporting periods as well as the amount of campaign cash entering the race (Michael Capuano entered the race with some money left over from his re-election to the House in 2008).
I actually kind of like the Russian spam on my blog. It’s like opening up a Christmas present — you never know what you’re going to get.
The first one I actually approved as a comment, because it was kind of fun and easy to translate it from Russian, even though it was clearly spam. It read:
тише,все ок!всем нравится,и мне!
which translates to English as:
quiet, everything is OK! everyone likes, and me!
This is much higher quality than the usual English spam. It has one complete sentence in it, “Quiet, everything is OK,” even though the second sentence kind of falls apart. But is this just part of the translation? Does “everyone likes and me” actually make sense in Russian? Yes, it’s possible that this is even higher quality spam in Russian. But in English, this last sentence makes the whole comment kind of catchy in a “all your base are belong to us” kind of way.
Did this comment actually make sense in response to the post? Not really. The post states that there is a report that was released. The comment is about a position taken, but no position was taken. But, hey, who can blame ‘em? Most posts on the web are about taking a position. And anyway, the comment was approved!
The second Russian spam comment came in as:
Я все понял и ни чего не понял:)
which translates to:
I understood everything and did not notice:)
This one also had good form. One good complete sentence — actually uses a conjunction correctly. The second phrase agrees and uses the same subject as the first without repeating. Emoticon at the end is a dead giveaway, though. And again, doesn’t really make sense with the page it was posted on.
And finally, the third one:
Я считаю, что Вы не правы. Давайте обсудим. Пишите мне в PM, поговорим.
in English:
I think you are wrong. Let’s discuss. Send me a PM, we’ll talk.
Very impressive. Three sentences, all complete! The first is a direct challenge — defend your position! Unfortunately, it’s a comment on the same post as the first one. There’s really nothing to be wrong about here, unless McKinsey did not release that report, but I’m pretty sure they did.
So the sentence structure is getting better, but, alas, there’s always some killer at the end of the Russian spam comment: an awkward last sentence, emoticon too close to the end of the sentence, or in this case, flubbing a shorthand expression. ”Send me a PM?” I think you mean IM. But, yes, dear web crawler, let’s keep the dialog open.
Nearly every time I was in a rural post office FedEx or UPS would show up, bring a load of packages to be delivered and pay the postage to have them delivered. I asked a few Pm’s [postmasters] about it, they each explained that it was cheaper for them to pay the Postal Service to deliver the packages than to have to drive their trucks sometimes miles into very remote areas.
Why can’t we have a nationwide wireless phone and data network equivalent to the USPS? This infrastructure would provide service to the rural and remote areas where none is available. It’s not as if AT&T and Verizon are interested in providing service to these areas. They could adopt the same model as FedEx and UPS and pay this federal wireless broadband entity for capacity in those areas on an as needed basis. Increasingly, safety and rescue operations are relying on cellular service to help them perform their tasks. National wireless coverage may become a necessity.
