2002 · 273 citations · 15 references
Natural SciencesComputer SciencePhysicsOptimizationRepresentation TheoryDigital Signal ProcessingDimensionality ReductionFourier AnalysisFourier Series MethodsSampling TheorySignal ProcessingSparse CodingSparse Signal ProcessingSparse Signal Representation
(MATH) We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal signal A of length N, such that $\|\signal-\repn\|_2^2$ is within the factor (1 +ε) of best possible $\|\signal-\repn_\opt\|_2^2$. Our algorithm can access A by reading its values on a sample set T ⊆[0,N), chosen randomly from a (non-product) distribution of our choice, independent of A. That is, we sample non-adaptively. The total time cost of the algorithm is polynomial in B log(N)log(M)ε (where M is the ratio of largest to smallest numerical quantity encountered), which implies a similar bound for the number of samples.
15
Communication in the Presence of Noise
Claude E. Shannon · Proceedings of the IRE · 1949 · 6.1K citations
Communications in the presence of noise
Claude E. Shannon · Medical Entomology and Zoology · 1949 · 1.2K citations
The space complexity of approximating the frequency moments
Noga Alon, Yossi Matias, Márió Szegedy · 1996 · 847 citations