Description
We discuss how sparse interpolation in computer algebra and exponential analysis in digital signal processing can cross-fertilize and lead to new results. The Nyquist constraint [11] is the digital signal processing equivalent of stating that the argument of a complex exponential exp(φ∆) with φ ∈ C and ∆ ∈ R+ can only be retrieved uniquely under the condition that |=(φ)|∆ < π. It governs signal processing since the beginning of the 20-th century. In the past two decades this constraint was first broken with the use of randomly collected signal samples [8, 2] and later for use with uniform samples [6].
The latter method closely relates to the original version of the exponential data fitting algorithm published in 1795 by the French mathematician de Prony [7], which is often cited in sparse interpolation research. In engineering applications it is mostly implemented using a structured generalized eigenvalue approach. Besides avoiding the Nyquist constraint, the new result in [6] also solves a number of remaining open problems in exponential analysis, which we plan to discuss.
In the identification, from given values fk ∈ C, of the nonlinear parameters φ1, . . . , φn ∈ C, the linear coefficients α1, . . . , αn ∈ C and the sparsity n ∈ N in the inverse problem
n∑
j=1
αj exp(φj k∆) = fk, k = 0, . . . , 2n − 1, . . . fk ∈ C, ∆ ∈ R+, (1)
several cases are considered to be hard [6, 1]: When some of the φj cluster, the identification and separation of these clustered φj becomes numerically ill-conditioned. We show how the problem may be reconditioned.
Retrieval of the correct value of n is difficult, and more so in case of clustered φj and noisy samples fk. Here, decimation of the data offers a way to obtain a reliable estimate of n automatically. Such decimation allows to divide and conquer the inverse problem statement. The smaller subproblems are largely independent and can be solved in parallel, leading to an improved complexity and efficiency.
At the same time, the sub-Nyquist Prony method proves to be robust with respect to outliers in the data. Making use of some approximation theory results [9, 10, Kn.Cu:rob:23], we can also validate the computation of the φj and αj .
The Nyquist constraint effectively restricts the bandwidth of the =(φj ). Therefore, avoiding the constraint offers so-called superresolution, or the possibility to unearth higher frequency components in the samples. All of the above can be generalized in several ways, to the use of more functions besides the exponential on the one hand, and to the solution of multdimensional inverse problems as in (1) on the other [5].
References
[1] M. Briani, A. Cuyt, F. Knaepkens, and W.-s. Lee. VEXPA: Validated EXPonential Analysis through regular subsampling. Signal Processing, 177: nr. 107722, 2020. (Published online July 17, 2020. Toolbox and experiments downloadable.).
[2] Emmanuel J. Cand`es, Justin Romberg, and Terence Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory, 52(2):489–509, 2006.
[3] Annie Cuyt and Wen-shin Lee. Smart data sampling and data reconstruction. US Patent 9,690,749.
[4] Annie Cuyt and Wen-shin Lee. Smart data sampling and data reconstruction. EP2745404B1.
[5] Annie Cuyt and Wen-shin Lee. Multivariate exponential analysis from the minimal number of samples. Adv. Comput. Math., 44:987–1002, 2018. (Published online
November 16, 2017. Toolbox and experiments downloadable.).
[6] Annie Cuyt and Wen-shin Lee. How to get high resolution results from sparse and coarsely sampled data. Appl. Comput. Harmon. Anal., 48:1066–1087, 2020. (Published online October 11, 2018. Toolbox and experiments downloadable.).
[7] R. de Prony. Essai exp´erimental et analytique sur les lois de la dilatabilite des fluides elastiques et sur celles de la force expansive de la vapeur de l’eau et de la vapeur de l’alkool, a differentes temp´eratures. J. Ec. Poly., 1(22):24–76, 1795.
[8] D. L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289–1306, 2006.
[9] J. Gilewicz and M. Pindor. Pad´e approximants and noise: a case of geometric series. J. Comput. Appl. Math., 87:199–214, 1997.
[10] J. Gilewicz and M. Pindor. Pad´e approximants and noise: rational functions. J. Comput. Appl. Math., 105:285–297, 1999.
[11] H. Nyquist. Certain topics in telegraph transmission theory. Trans. Am. Inst. Electr. Eng., 47(2):617–644, April 1928
