An official website of the United States government
We study the problem of sampling a bandlimited graph signal in the presence of noise, where the objective is to select a node subset of prescribed cardinality that minimizes the signal reconstruction mean squared error (MSE). To that end, we formulate the task at hand as the minimization of MSE subject to binary constraints, and approximate the resulting NP-hard problem via semidefinite programming (SDP) relaxation. Moreover, we provide an alternative formulation based on maximizing a monotone weak submodular function and propose a randomized-greedy algorithm to find a sub-optimal subset. We then derive a worst-case performance guarantee on the MSE returned by the randomized greedy algorithm for general non-stationary graph signals. The efficacy of the proposed methods is illustrated through numerical simulations on synthetic and realworld graphs. Notably, the randomized greedy algorithm yields an order-of-magnitude speedup over state-of-the-art greedy sampling schemes, while incurring only a marginal MSE performance loss.
more »
« less
A novel scheme for support identification and iterative sampling of bandlimited graph signals
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
- PAR ID:
- 10087989
- Date Published:
- Journal Name:
- 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP)
- Page Range / eLocation ID:
- 778 - 782
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract PurposeForward and backprojections are the basis of all model‐based iterative reconstruction (MBIR) methods. However, computing these accurately is time‐consuming. In this paper, we present a method for MBIR in parallel X‐ray beam geometry that utilizes a Gram filter to efficiently implement forward and backprojection. MethodsWe propose using voxel‐basis and modeling its footprint in a box spline framework to calculate the Gram filter exactly and improve the performance of backprojection. In the special case of parallel X‐ray beam geometry, the forward and backprojection can be implemented by an estimated Gram filter efficiently if the sinogram signal is bandlimited. In this paper, a specialized sinogram interpolation method is proposed to eliminate the bandlimited prerequisite and thus improve the reconstruction accuracy. We build on this idea by utilizing the continuity of the voxel‐basis' footprint, which provides a more accurate sinogram interpolation and further improves the efficiency and quality of backprojection. In addition, the detector blur effect can be efficiently accounted for in our method to better handle realistic scenarios. ResultsThe proposed method is tested on both phantom and real computed tomography (CT) images under different resolutions, sinogram sampling steps, and noise levels. The proposed method consistently outperforms other state‐of‐the‐art projection models in terms of speed and accuracy for both backprojection and reconstruction. ConclusionsWe proposed a iterative reconstruction methodology for 3D parallel‐beam X‐ray CT reconstruction. Our experimental results demonstrate that the proposed methodology is accurate, fast, and reproducible, and outperforms alternative state‐of‐the‐art projection models on both backprojection and reconstruction results significantly.more » « less
-
In numerous graph signal processing applications, data is often missing for a variety of reasons, and predicting the missing data is essential. In this paper, we consider data on graphs modeled as bandlimited graph signals. Predicting or reconstructing the unknown signal values for such a model requires an estimate of the signal bandwidth. In this paper, we address the problem of estimating the reconstruction errors, minimizing which would thereby provide an estimate of the signal bandwidth. In doing so, we design a cross-validation approach needed for stable graph signal reconstruction and propose a method for estimating the reconstruction errors for different choices of signal bandwidth. Using this technique, we are able to estimate the reconstruction error on a variety of real-world graphs.more » « less
-
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
-
Sampling in shift-invariant spaces is a realistic model for signals with smooth spectrum. In this paper, we consider phaseless sampling and reconstruction of real-valued signals in a high-dimensional shift-invariant space from their magnitude measurements on the whole Euclidean space and from their phaseless samples taken on a discrete set with finite sampling density. The determination of a signal in a shift-invariant space, up to a sign, by its magnitude measurements on the whole Euclidean space has been shown in the literature to be equivalent to its nonseparability. In this paper, we introduce an undirected graph associated with the signal in a shift-invariant space and use connectivity of the graph to characterize nonseparability of the signal. Under the local complement property assumption on a shift-invariant space, we find a discrete set with finite sampling density such that nonseparable signals in the shift-invariant space can be reconstructed in a stable way from their phaseless samples taken on that set. In this paper, we also propose a reconstruction algorithm which provides an approximation to the original signal when its noisy phaseless samples are available only. Finally, numerical simulations are performed to demonstrate the robustness of the proposed algorithm to reconstruct box spline signals from their noisy phaseless samples.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/GlobalSIP.2018.8646488
