Paper: http://arxiv.org/pdf/1201.2501v1 http://arxiv.org/pdf/1201.2501v1 It starts by dividing the spectrum into frequency bins, and assumes that there is usua

Paper: http://arxiv.org/pdf/1201.2501v1 http://arxiv.org/pdf/1201.2501v1 It starts by dividing the spectrum into frequency bins, and assumes that there is usually 0 or 1 non-zero coefficients in each bin. It wasn't clear to me what happens when a large number of non-zero coefficients are clustered together in one bin. Can O(k log n) still be achieved when most frequencies are clustered?