"Science is hard and getting harder, and to make sense of it, you need to be taught about the basics. There is no time anymore to figure it out for yourself."
No, that's the part that's missing. Everyone expects to have things handed to them. There is no more "figure it out for yourself." The worst possible thing you can do if you're trying to train future scientists is not teach them how to figure things out for themselves.
As far as I know, the only group seriously in favour of group marriages are some of the more fundamentalist Mormons. They're not much for gay marriage though.
So when you say "they" you mean... people who disagree with you?
That's the idea. "Sparsity" doesn't mean it has lots of zeros, it means it has lots of values that you don't particularly care about (usually those that are close to zero.
Virtually all images of any interest (anything that's not just random noise) is sparse in some domain, and the majority are quite sparse in the frequency domain. So yes, this algorithm should help quite a bit.
No, it doesn't trivialize the result. This is not an improvement in O order, as the FFT is over the DFT. It's an improvement in the average case time. Worst case performance is the same order as the FFT. I suspect that for most applications the speedup really is a factor X, where X is closely related to the sparsity of the signal.
"If you're keen on this sort of thing, read a bit about solving systems of linear equations, and you will hopefully be able to look at the problem, exclaim "this is trivial!""
Noooo! That's not the kind of understanding the OP seems to want. Someone with a really deep understanding of linear algebra might be able to make the connection between the matrix formulation of the DFT and the intuitive understanding of what's actually going on, but I've almost universally found that isn't the case. The matrix formulation is very nice for doing things WITH the DFT, but not for understanding the DFT itself.
To get an intuitive understanding of the DFT you need to sit down with Python or MatLab or whatever your language of choice is, make a signal, calculate the correlations with some sinusoids, then add those sinusoids together, etc.
"You construct the matrix A" is very often the best way to prove something is true, but I've found is very rarely, if ever, the way to teach someone to understand WHY it's true.
Take a signal. You can figure out the amplitude of any particular frequency in that signal by correlating it with a sinusoid of the frequency of interest. Correlation (in this context) is just multiplying the two signals together, point by point, then summing up. The Fourier transform basically says that if you want to know what the frequency spectrum is, you do this basic operation for all the frequencies in the spectrum. The discrete Fourier transform tells you, based on the sampling you did on the signal, which frequencies you need to calculate so you only have to do a finite number.
The fast Fourier transform is a neat trick based on the observation that the discrete spectrum of the whole signal can be trivially calculated from the discrete spectra of the original signal either divided in two halves or into odd and even samples. Since the DFT is a N^2 operation, it's usually faster to do two DFTs of length N/2 than it is to do one of length N. You keep applying this trick, dividing the signals in half, then the halves in half, etc. until it's not worth dividing them any further, usually when they're 2 or 4 points long, although you can go all the way down to one point if you want: the Fourier transform of a signal sample is a null operation.
A signal is sparse if it requires less than the naively expected amount of information to represent adequately. Virtually all interesting signals are sparse, video especially so.
Basically what you do now is calculate the transform (usually a DCT, but fast DCT algorithms usually use the FFT anyway), then throw away the small coefficients. What this algorithm does is not calculate (most of) those small coefficients in the first place.
A good optimized FFT is generally more efficient than the naive DFT algorithm on power of two signals with > 4 samples on modern hardware. By the time you hit 16 you should definitely be in the FFT range, particularly if you're doing a bunch of them. If you look at the FFTw library, most of the algorithms for transforming power of two signals are radix-4.
Nitpick: EVERYTHING that's worth compressing is sparse. Compression exploits the sparsity of almost every signal we find interesting. You can go ahead and lossily compress non-sparse data, but you won't be happy with the result.
Most fast DCT algorithms are actually a slight modification of the FFT algorithm, so it's very, very likely that the algorithm in the article would work for DCTs as well.
What you say isn't actually wrong, but it's not talking about the same thing. The frequency resolution you can achieve is determined by the amount of time you observe a signal, regardless of how you sample it (the principle holds for ideal continuous signals as well) and conversely, the temporal resolution of a signal you reconstruct is limited by the highest frequency you observe. The DFT (the FFT is just a fast algorithm for the DFT and produces the same result) represents a spectrum efficiently by providing samples that match this fundamental limitation.
He's not saying that the time-frequency resolution tradeoff is due to quantum physics effects. He's saying that the two uncertainty principles are related. They are. We're talking about pure theory here, with no engineering difficulties. And yes, the fundamental math is information theory and Nyquist (which is ALSO very similar to the fundamental math of quantum physics). The equations for the two uncertainty principles have exactly the same form.
An ideal, theoretical, continuous signal that is time-limited has limited spectral resolution. An ideal, theoretical, continuous spectrum has limited temporal resolution.
It's a silly distinction. Has your doctor ever asked you about your family history? Genetic based personalized medicine. Has your doctor ever asked you if you smoked, how much you exercise, what you eat? Lifestyle based personalized medicine.
"Personalized medicine" is just coming up with better tests to do these things. Genetics had a heyday where it was the cause of (and solution to) everything. That's ending as we learn more.
There's a story about Nike that illustrates the dangers of using means (which is what your data uses as "average") instead of medians. Something about tens of thousands of third world workers making peanuts, Michael Jordan making bazillions, and Nike saying "look, our average wage is pretty good!"
Just because some rich people do really well doesn't mean you're doing a good job. And you neglect to mention that the US pays a LOT more for the health care it provides than pretty much anybody else.
Slashdot Mirror
"Science is hard and getting harder, and to make sense of it, you need to be taught about the basics. There is no time anymore to figure it out for yourself."
No, that's the part that's missing. Everyone expects to have things handed to them. There is no more "figure it out for yourself." The worst possible thing you can do if you're trying to train future scientists is not teach them how to figure things out for themselves.
Not never... there was a probably release of an Ebola-type virus in Reston, Virginia IIRC.
"it only stands to reason that 'uncountable' should be extended to also have a plural form."
What's wrong with "uncountables?"
"the singular would be virius"
That is a pretty awesome word though. We should really find a use for it.
As far as I know, the only group seriously in favour of group marriages are some of the more fundamentalist Mormons. They're not much for gay marriage though.
So when you say "they" you mean... people who disagree with you?
Multiple backups. Always.
The null transform beats them both. So does the plus-one transform. What's your point?
That's the idea. "Sparsity" doesn't mean it has lots of zeros, it means it has lots of values that you don't particularly care about (usually those that are close to zero.
Virtually all images of any interest (anything that's not just random noise) is sparse in some domain, and the majority are quite sparse in the frequency domain. So yes, this algorithm should help quite a bit.
So many people have the highly irritating habit of not writing either specific algorithms or sample code to go along with their papers.
No, it doesn't trivialize the result. This is not an improvement in O order, as the FFT is over the DFT. It's an improvement in the average case time. Worst case performance is the same order as the FFT. I suspect that for most applications the speedup really is a factor X, where X is closely related to the sparsity of the signal.
The math can be instructive, but it's tough to get a practical feeling for the CFT because you need a bunch of optical equipment. ;)
"If you're keen on this sort of thing, read a bit about solving systems of linear equations, and you will hopefully be able to look at the problem, exclaim "this is trivial!""
Noooo! That's not the kind of understanding the OP seems to want. Someone with a really deep understanding of linear algebra might be able to make the connection between the matrix formulation of the DFT and the intuitive understanding of what's actually going on, but I've almost universally found that isn't the case. The matrix formulation is very nice for doing things WITH the DFT, but not for understanding the DFT itself.
To get an intuitive understanding of the DFT you need to sit down with Python or MatLab or whatever your language of choice is, make a signal, calculate the correlations with some sinusoids, then add those sinusoids together, etc.
"You construct the matrix A" is very often the best way to prove something is true, but I've found is very rarely, if ever, the way to teach someone to understand WHY it's true.
Whoops. Replied to a reply to your post by accident. See: http://science.slashdot.org/comments.pl?sid=2630002&cid=38767088
Take a signal. You can figure out the amplitude of any particular frequency in that signal by correlating it with a sinusoid of the frequency of interest. Correlation (in this context) is just multiplying the two signals together, point by point, then summing up. The Fourier transform basically says that if you want to know what the frequency spectrum is, you do this basic operation for all the frequencies in the spectrum. The discrete Fourier transform tells you, based on the sampling you did on the signal, which frequencies you need to calculate so you only have to do a finite number.
The fast Fourier transform is a neat trick based on the observation that the discrete spectrum of the whole signal can be trivially calculated from the discrete spectra of the original signal either divided in two halves or into odd and even samples. Since the DFT is a N^2 operation, it's usually faster to do two DFTs of length N/2 than it is to do one of length N. You keep applying this trick, dividing the signals in half, then the halves in half, etc. until it's not worth dividing them any further, usually when they're 2 or 4 points long, although you can go all the way down to one point if you want: the Fourier transform of a signal sample is a null operation.
A signal is sparse if it requires less than the naively expected amount of information to represent adequately. Virtually all interesting signals are sparse, video especially so.
Basically what you do now is calculate the transform (usually a DCT, but fast DCT algorithms usually use the FFT anyway), then throw away the small coefficients. What this algorithm does is not calculate (most of) those small coefficients in the first place.
A good optimized FFT is generally more efficient than the naive DFT algorithm on power of two signals with > 4 samples on modern hardware. By the time you hit 16 you should definitely be in the FFT range, particularly if you're doing a bunch of them. If you look at the FFTw library, most of the algorithms for transforming power of two signals are radix-4.
Nitpick: EVERYTHING that's worth compressing is sparse. Compression exploits the sparsity of almost every signal we find interesting. You can go ahead and lossily compress non-sparse data, but you won't be happy with the result.
Most fast DCT algorithms are actually a slight modification of the FFT algorithm, so it's very, very likely that the algorithm in the article would work for DCTs as well.
What you say isn't actually wrong, but it's not talking about the same thing. The frequency resolution you can achieve is determined by the amount of time you observe a signal, regardless of how you sample it (the principle holds for ideal continuous signals as well) and conversely, the temporal resolution of a signal you reconstruct is limited by the highest frequency you observe. The DFT (the FFT is just a fast algorithm for the DFT and produces the same result) represents a spectrum efficiently by providing samples that match this fundamental limitation.
He's not saying that the time-frequency resolution tradeoff is due to quantum physics effects. He's saying that the two uncertainty principles are related. They are. We're talking about pure theory here, with no engineering difficulties. And yes, the fundamental math is information theory and Nyquist (which is ALSO very similar to the fundamental math of quantum physics). The equations for the two uncertainty principles have exactly the same form.
An ideal, theoretical, continuous signal that is time-limited has limited spectral resolution. An ideal, theoretical, continuous spectrum has limited temporal resolution.
The same. The frequency-time resolution tradeoff is a fundamental property, and the short-time DFT makes that tradeoff efficiently.
It's a silly distinction. Has your doctor ever asked you about your family history? Genetic based personalized medicine. Has your doctor ever asked you if you smoked, how much you exercise, what you eat? Lifestyle based personalized medicine.
"Personalized medicine" is just coming up with better tests to do these things. Genetics had a heyday where it was the cause of (and solution to) everything. That's ending as we learn more.
"so for an average person"
There's a story about Nike that illustrates the dangers of using means (which is what your data uses as "average") instead of medians. Something about tens of thousands of third world workers making peanuts, Michael Jordan making bazillions, and Nike saying "look, our average wage is pretty good!"
Just because some rich people do really well doesn't mean you're doing a good job. And you neglect to mention that the US pays a LOT more for the health care it provides than pretty much anybody else.
HDMI is only HDMI if you're hooking the thing up to a fairly crappy TV. Otherwise there are lots of different standards.
DisplayPort, on the other hand, makes a lot more sense than any of them.