Abstract
We consider non-uniform random sampling in a signal space with finite rate of innovation \(V^{2}(\varLambda,\varPhi) \subset{\mathrm {L}}^{2}(\mathbb {R}^{d})\) generated by a series of functions \(\varPhi=(\phi_{\lambda})_{\lambda \in\varLambda}\). A subset \(V_{R,\delta}^{2}(\varLambda,\varPhi)\) of \(V^{2}(\varLambda,\varPhi)\) is consisting of functions concentrates at least \(1-\delta\) of the whole energy in a cube with side lengths \(R\). Under mild assumptions on the generators and the probability distribution, we show that for \(R\) sufficiently large, taking \(O(R^{d} \log(R^{d}))\) many samples with such the non-uniform distribution yields a sampling set for \(V_{R,\delta}^{2}(\varLambda,\varPhi)\) with high probability. We impose compact support on the generators as an additional constraint for obtaining a reconstruction algorithm from non-uniform random sampling with high probability.
Similar content being viewed by others
References
Aldroubi, A., Gröchenig, K.: Nonuniform sampling and reconstruction in shift-invariant spaces. SIAM Rev. 43(4), 585–620 (2001)
Baechler, G., Scholefield, A., Baboulaz, L., Vetterli, M.: Sampling and exact reconstruction of pulses with variable width. IEEE Trans. Signal Process. 65(10), 2629–2644 (2017)
Bass, R.F., Gröchenig, K.: Relevant sampling of band-limited functions. Ill. J. Math. 57(1), 43–58 (2013)
Bernardi, O., Giménez, O.: A linear algorithm for the random sampling from regular languages. Algorithmica 62(1–2), 130–145 (2012)
Bi, N., Nashed, M.Z., Sun, Q.Y.: Reconstructing signals with finite rate of innovation from noisy samples. Acta Appl. Math. 107(1–3), 339–372 (2009)
Fang, K.T., Ma, C.X., Winker, P.: Centered \(L_{2}\)-discrepancy of random sampling and Latin hypercube design, and construction of uniform designs. Math. Comput. 71(237), 275–296 (2002)
Führ, H., Xian, J.: Quantifying invariance properties of shift-invariant spaces. Appl. Comput. Harmon. Anal. 36, 514–521 (2014)
Führ, H., Xian, J.: Relevant sampling in finitedly generated shift-invariant spaces. J. Approx. Theory 240, 1–15 (2019)
Gröchenig, K., Schwab, H.: Fast local reconstruction methods for nonuniform sampling in shift-invariant spaces. SIAM J. Matrix Anal. Appl. 24(4), 899–913 (2003)
Li, Y.X., Wen, J.M., Xian, J.: Reconstruction from convolution random sampling in local shift invariant spaces. Inverse Problems (2019). https://iopscience.iop.org/article/10.1088/1361-6420/ab40f7/meta
Moskowitz, B., Caflisch, R.E.: Smoothness and dimension reduction in quasi-Monte Carlo methods. Math. Comput. Model. 23(8), 37–54 (1996)
Mulleti, S., Seelamantula, C.S.: Ellipse fitting using the finite rate of innovation sampling principle. IEEE Trans. Image Process. 25(3), 1451–1464 (2016)
Pedergnana, M., García, S.G.: Smart sampling and incremental function learning for very large high dimensional data. Neural Netw. 78, 75–87 (2016)
Romero, V.J., Burkardt, J.V., Gunzburger, M.D., Peterson, J.S.: Comparison of pure and “Latinized” centroidal Voronoi tessellation against various other statistical sampling methods. Reliab. Eng. Syst. Saf. 91(10–11), 1266–1280 (2006)
Rudresh, S., Seelamantula, C.S.: Finite-rate-of-innovation-based super-resolution radar imaging. IEEE Trans. Signal Process. 65(19), 5021–5033 (2017)
Schumaker, L.L.: Spline Functions: Basic Theory. John Wiley & Sons, New York (1981)
Sun, Q.Y.: Nonuniform average sampling and reconstruction of signals with finite rate of innovation. SIAM J. Math. Anal. 38(5), 1389–1422 (2006)
Sun, Q.Y.: Wiener’s lemma for infinite matrices. Trans. Am. Math. Soc. 359(7), 3099–3123 (2007)
Sun, Q.Y.: Frames in spaces with finite rate of innovation. Adv. Comput. Math. 28(4), 301–329 (2008)
Sun, W.C.: Local sampling theorems for spaces generated by splines with arbitrary knots. Math. Comput. 78(265), 225–239 (2009)
Sun, W.C., Zhou, X.W.: Characterization of local sampling sequences for spline subspaces. Adv. Comput. Math. 30(2), 153–175 (2009)
Tropp, J.A.: User-friendly tail bounds for sums of random matrices. Found. Comput. Math. 12(4), 389–434 (2012)
Vetterli, M., Marziliano, P., Blu, T.: Sampling signals with finite rate of innovation. IEEE Trans. Signal Process. 50(6), 1417–1428 (2002)
Xian, J., Li, S.: Sampling set conditions in weighted finitely generated shift-invariant spaces and their applications. Appl. Comput. Harmon. Anal. 23(2), 171–180 (2007)
Yang, J.B.: Random sampling and reconstruction in multiply generated shift-invariant spaces. Anal. Appl. 17(2) 323–347 (2019)
Acknowledgements
The authors would like to thank the reviewers for their valuable comments and suggestions that led to the improvement of this paper. The corresponding author Jun Xian is partially supported by the National Natural Science Foundation of China (11422102, 11631015, 11871481); the Guangdong Provincial Government of China through the Computational Science Innovative Research Team program, China; and the Guangdong Province Key Laboratory of Computational Science, China.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix. Some Properties of the Signal Spaces \(V^{2}(\varLambda,\varPhi)\)
Appendix. Some Properties of the Signal Spaces \(V^{2}(\varLambda,\varPhi)\)
We assume that \(\varPhi:=\{\phi_{\lambda}\}_{\lambda\in\varLambda}\) is a Riesz basis of \(V^{2}(\varLambda,\varPhi)\), therefore there exists a dual Riesz basis \(\widetilde{\varPhi}=\{\widetilde{\phi }_{\lambda}\}_{\lambda\in\varLambda}\). Thus we have that for all \(f \in V^{2}(\varLambda,\varPhi)\), such that
We can easily see that for all \(1\leq q' \leq q \leq\infty\), \(\infty \geq p' \geq p \geq1\) and \(u'(x)\leq u(x), \forall x \in \mathbb {R}^{d}\), we have \(\|\varPhi\|_{q',p',u'}\leq\|\varPhi\|_{q,p,u}\). Moreover, by [19, Theorem 4.1], we have that if \({\|\varPhi\| _{q,p,u}<\infty}\), then so is the same norm of the dual Riesz basis, or to say \(\|\widetilde{\varPhi}\|_{q,p,u}<\infty\).
For convenience of the main proof, we will show some properties of the space \(V^{2}(\varLambda,\varPhi)\) under the assumptions of the generators in Sect. 2.2.
Proposition 22
If \(f \in{\mathrm{L}}^{2}(\mathbb {R}^{d})\), \(\varPhi=\{\phi_{\lambda}\} \)satisfying (A.0) and \(\|\varPhi\|_{2,1,u_{0}}<\infty\), then we have:
and
Proof
We firstly prove (22). In fact, we have
A similar method is used in the proof of [18, Theorem 2.4(iii)]. Similar to the proof above, we can prove (23) as well. □
Proposition 23
For every \(f \in V^{2}(\varLambda,\varPhi)\)and every subset \(\varGamma\subset \mathbb {R}^{d}\)where the absolute covering index \(N_{0}(\varGamma)\)defined in (3) is finite, we have
Proof
First we consider \(\varGamma\) with \(N_{0}(\varGamma)=1\), that is, for any \(k\in \mathbb {Z}^{d}\), there is at most one point in \(\varGamma\cap (k+[0,1]^{d})\). Let \(c(\lambda)=\langle f,\widetilde{\phi}_{\lambda}\rangle\), then \(f=\sum_{\lambda\in\varLambda}c(\lambda)\phi _{\lambda}\). Similar to the proof of Proposition 22, we have
where the last inequality is derived from the conclusion of Proposition 22.
For a general subset \(\varGamma\), we can split it into at most \(N_{0}(\varGamma)\) non-intersect parts each of which has absolute covering index 1. Then sum the function value of each part respectively, sum all of them all together and we get the final conclusion. □
Proposition 24
\(V^{2}(\varLambda,\varPhi)\)is a reproducing kernel space, or to say there exists a family \((v_{x})_{x\in \mathbb {R}^{d}}\subset V^{2}(\varLambda,\varPhi)\)such that \(f(x)=\langle f,v_{x}\rangle ,\forall f\in V^{2}(\varLambda,\varPhi)\)and \(\|v_{x}\|_{2}^{2}\leq D_{2}\)almost everywhere. Moreover, we have \(\|f\|_{\infty}^{2}\leq D_{2}\|f\|_{2}^{2}\)for all \(f\in V^{2}(\varLambda,\varPhi)\).
Proof
We define that \(v_{x}(y)=\sum_{\lambda\in\varLambda}\widetilde{\phi }_{\lambda}(y)\overline{\phi_{\lambda}(x)}\), and \(w_{x}(y)=\sum_{\lambda \in\varLambda}\phi_{\lambda}(y)\overline{\widetilde{\phi}_{\lambda}(x)}\). For all \(f\in V^{2}(\varLambda,\varPhi)\), we have that
Similarly, we have
Therefore, \(\langle f,w_{x}-v_{x}\rangle=0\) holds for all \(f\in V^{2}(\varLambda,\varPhi)\). However, both \(v_{x}\) and \(w_{x}\) are in \(V^{2}(\varLambda,\varPhi)\) by definition, then \(w_{x}-v_{x}\in V^{2}(\varLambda,\varPhi)\). So \(\langle w_{x}-v_{x},w_{x}-v_{x}\rangle=0\), or \({w_{x}-v_{x}=0}\). Therefore \(w_{x}=v_{x}\), which implies \(v_{x}(y)=\sum_{\lambda\in\varLambda }\phi_{\lambda}(y)\overline{\widetilde{\phi}_{\lambda}(x)}\) as well.
We now show that \(v(x)_{x\in \mathbb {R}^{d}}\) is a reproducing kernel. For fixed \(x\in \mathbb {R}^{d}\), we have
By \(\|\varPhi\|_{\infty,1,u_{0}}< \infty\), we can change the order of the sum and the integration. So we can obtain that
Thus \(\mathrm{ess}\,\mathrm{sup}_{x\in \mathbb {R}^{d}}\|v_{x}\|_{2}^{2}\leq D_{2}<\infty\). Therefore \((v_{x})_{x\in \mathbb {R}^{d}}\) is a reproducing kernel of \(V^{2}(\varPhi,\varLambda)\). Moreover, we have
□
Rights and permissions
About this article
Cite this article
Lu, Y., Xian, J. Non-uniform Random Sampling and Reconstruction in Signal Spaces with Finite Rate of Innovation. Acta Appl Math 169, 247–277 (2020). https://doi.org/10.1007/s10440-019-00298-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10440-019-00298-6
Keywords
- Random sampling
- Non-uniform sampling
- Spaces with finite rate of innovation
- Non-uniform distribution
- Reconstruction algorithm