More Like this

1. Phase retrieval of real-valued signals in a shift-invariant space

   https://doi.org/10.1016/j.acha.2018.11.002  

   Chen, Yang ; Cheng, Cheng ; Sun, Qiyu ; Wang, Haichao ( July 2020 , Applied and computational harmonic analysis)

   In this paper, we consider an infinite-dimensional phase retrieval problem to reconstruct real-valued signals living in a shift-invariant space from their phaseless samples taken either on the whole line or on a discrete set with finite sampling density. We characterize all phase retrievable signals in a real-valued shift-invariant space using their nonseparability. For nonseparable signals generated by some function with support length L, we show that they can be well approximated, up to a sign, from their noisy phaseless samples taken on a discrete set with sampling density 2L-1 . In this paper, we also propose an algorithm with linear computational complexity to reconstruct nonseparable signals in a shift-invariant space from their phaseless samples corrupted by bounded noises. 

   more » « less
2. A novel scheme for support identification and iterative sampling of bandlimited graph signals

   https://doi.org/10.1109/GlobalSIP.2018.8646488  

   Hashemi, Abolfazl ; Shafipour, Rasoul ; Vikalo, Haris ; Mateos, Gonzalo ( February 2019 , 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP))

   We study the problem of sampling and reconstruction of bandlimited graph signals where the objective is to select a node subset of prescribed cardinality that ensures interpolation of the original signal with the lowest reconstruction error. We propose an efficient iterative selection sampling approach and show that in the noiseless case the original signal is exactly recovered from the set of selected nodes. In the case of noisy measurements, a bound on the reconstruction error of the proposed algorithm is established. We further address the support identification of the bandlimited signal with unknown support and show that under a pragmatic sufficient condition, the proposed framework requires minimal number of samples to perfectly identify the support. The efficacy of the proposed methods is illustrated through numerical simulations on synthetic and real-world graphs. 

   more » « less
3. Adaptive Metrics for Adaptive Samples

   https://doi.org/10.3390/a13080200  

   Cavanna, Nicholas J. ; Sheehy, Donald R. ( August 2020 , Algorithms)

   null (Ed.)

   We generalize the local-feature size definition of adaptive sampling used in surface reconstruction to relate it to an alternative metric on Euclidean space. In the new metric, adaptive samples become uniform samples, making it simpler both to give adaptive sampling versions of homological inference results and to prove topological guarantees using the critical points theory of distance functions. This ultimately leads to an algorithm for homology inference from samples whose spacing depends on their distance to a discrete representation of the complement space. 

   more » « less
4. Spatially distributed sampling and reconstruction

   https://doi.org/https://doi.org/10.1016/j.acha.2017.07.007  

   Cheng, Cheng ; Jiang, Yinchun ; Sun, Qiyu ( July 2019 , Applied and computational harmonic analysis)

   A spatially distributed network contains a large amount of agents with limited sensing, data processing, and communication capabilities. Recent technological advances have opened up possibilities to deploy spatially distributed networks for signal sampling and reconstruction. In this paper, we introduce a graph structure for a distributed sampling and reconstruction system by coupling agents in a spatially distributed network with innovative positions of signals. A fundamental problem in sampling theory is the robustness of signal reconstruction in the presence of sampling noises. For a distributed sampling and reconstruction system, the robustness could be reduced to the stability of its sensing matrix. In this paper, we split a distributed sampling and reconstruction system into a family of overlapping smaller subsystems, and we show that the stability of the sensing matrix holds if and only if its quasi-restrictions to those subsystems have uniform stability. This new stability criterion could be pivotal for the design of a robust distributed sampling and reconstruction system against supplement, replacement and impairment of agents, as we only need to check the uniform stability of affected subsystems. In this paper, we also propose an exponentially convergent distributed algorithm for signal reconstruction, that provides a suboptimal approximation to the original signal in the presence of bounded sampling noises. 

   more » « less
5. A Poincare Inequality and Consistency Results for Signal Sampling on Large Graphs

   Le, T ; Ruiz, Luana ; Jegelka, Stefanie ( May 2024 , International Conference on Learning Representations (ICLR))

   Large-scale graph machine learning is challenging as the complexity of learning models scales with the graph size. Subsampling the graph is a viable alternative, but sampling on graphs is nontrivial as graphs are non-Euclidean. Existing graph sampling techniques require not only computing the spectra of large matrices but also repeating these computations when the graph changes, e.g., grows. In this pa- per, we introduce a signal sampling theory for a type of graph limit—the graphon. We prove a Poincare ́ inequality for graphon signals and show that complements of node subsets satisfying this inequality are unique sampling sets for Paley-Wiener spaces of graphon signals. Exploiting connections with spectral clustering and Gaussian elimination, we prove that such sampling sets are consistent in the sense that unique sampling sets on a convergent graph sequence converge to unique sampling sets on the graphon. We then propose a related graphon signal sampling algorithm for large graphs, and demonstrate its good empirical performance on graph machine learning tasks. 

   more » « less