We focus on a multidimensional field with uncorrelated spectrum and study the quality of the reconstructed signal when the field samples are irregularly spaced and affected by independent and identically distributed noise. More specifically, we apply linear reconstruction techniques and take the mean-square error (MSE) of the field estimate as a metric to evaluate the signal reconstruction quality. We find that the MSE analysis could be carried out by using the closed-form expression of the eigenvalue distribution of the matrix representing the sampling system. Unfortunately, such distribution is still unknown. Thus, we first derive a closed-form expression of the distribution moments, and we find that the eigenvalue distribution tends to the Marcenko-Pastur distribution as the field dimension goes to infinity. Finally, by using our approach, we derive a tight approximation to the MSE of the reconstructed field.
The goal of this work is to provide an analytical study on the reconstruction quality of a multidimensional physical field, with uncorrelated spectrum. The field samples are (i) irregularly spaced, since they are gathered by a randomly deployed sensor network and (ii) affected by i.i.d. noise. The sink node receives the field samples and runs the reconstruction algorithm in a centralized manner. Our major contributions with respect to previous work are as follows. [1.] Given a @math -dimensional problem formulation, we obtain analytical expressions for the moments of the eigenvalue distribution of the reconstruction matrix. Using the expressions of the moments, we show that the eigenvalue distribution tends to the Mar c enko-Pastur distribution @cite_26 as the field dimension @math . [2.] We apply our results to the study of the quality of a reconstructed field and derive a tight approximation to the MSE of the estimated field.
@cite_26
2060581589
We consider wireless sensor networks whose nodes are randomly deployed and, thus, provide an irregular sampling of the sensed field. The field is assumed to be bandlimited; a sink node collects the data gathered by the sensors and reconstructs the field by using a technique based on linear filtering. By taking the mean square error (MSE) as performance metric, we evaluate the effect of quasi-equally spaced sensor layouts on the quality of the reconstructed signal. The MSE is derived through asymptotic analysis for different sensor spatial distributions, and for two of them we are able to obtain an approximate closed form expression. The case of uniformly distributed sensors is also considered for the sake of comparison. The validity of our asymptotic analysis is shown by comparison against numerical results and it is proven to hold even for a small number of nodes. Finally, with the help of a simple example, we show the key role that our results play in the deployment of sensor networks. We consider the problem of obtaining a high quality estimates of band-limited sensor fields when sensor measurements are noisy and the nodes are irregularly deployed and subject to random motion. We consider the mean square error (MSE) of the estimate and we analytically derive the performance of several reconstruction estimation techniques based on linear filtering. For each technique, we obtain the mean value of the MSE, as well as its asymptotic expression in the case where the field bandwidth and the number of sensors grow to infinity, while their ratio is kept constant. Our results provide useful guidelines for the design of sensor networks when many system parameters have to be traded off. Distributed sampling and reconstruction of a physical field using an array of sensors is a problem of considerable interest in environmental monitoring applications of sensor networks. Our recent work has focused on the sampling of bandlimited sensor fields. However, sensor fields are not perfectly bandlimited but typically have rapidly decaying spectra. In a classical sampling set-up it is possible to precede the A D sampling operation with an appropriate analog anti-aliasing filter. However, in the case of sensor networks, this is infeasible since sampling must precede filtering. We show that even though the effects of aliasing on the reconstruction cannot be prevented due to the "filter-less" sampling constraint, they can be suitably controlled by oversampling and carefully reconstructing the field from the samples. We show using a dither-based scheme that it is possible to estimate non-bandlimited fields with a precision that depends on how fast the spectral content of the field decays. We develop a framework for analyzing non-bandlimited fields that lead to upper bounds on the maximum pointwise error for a spatial bit rate of R bits meter. We present results for fields with exponentially decaying spectra as an illustration. In particular, we show that for fields f(t) with exponential tails; i.e., F( spl omega ) < spl pi spl alpha sup - spl alpha | spl omega | , the maximum pointwise error decays as c2e sup -a sub 1 spl radic R+ c3 1 spl radic R (e sup -2a sub 1 spl radic R) with spatial bit rate R bits meter. Finally, we show that for fields with spectra that have a finite second moment, the distortion decreases as O((1 N) sup 2 3 ) as the density of sensors, N, scales up to infinity . We show that if D is the targeted non-zero distortion, then the required (finite) rate R scales as O (1 spl radic D log 1 D). In this paper we investigate the capability of large-scale sensor networks to measure and transport a two-dimensional field. We consider a data-gathering wireless sensor network in which densely deployed sensors take periodic samples of the sensed field, and then scalar quantize, encode and transmit them to a single receiver central controller where snapshot images of the sensed field are reconstructed. The quality of the reconstructed field is limited by the ability of the encoder to compress the data to a rate less than the single-receiver transport capacity of the network. Subject to a constraint on the quality of the reconstructed field, we are interested in how fast data can be collected (or equivalently how closely in time these snapshots can be taken) due to the limitation just mentioned. As the sensor density increases to infinity, more sensors send data to the central controller. However, the data is more correlated, and the encoder can do more compression. The question is: Can the encoder compress sufficiently to meet the limit imposed by the transport capacity? Alternatively, how long does it take to transport one snapshot? We show that as the density increases to infinity, the total number of bits required to attain a given quality also increases to infinity under any compression scheme. At the same time, the single-receiver transport capacity of the network remains constant as the density increases. We therefore conclude that for the given scenario, even though the correlation between sensor data increases as the density increases, any data compression scheme is insufficient to transport the required amount of data for the given quality. Equivalently, the amount of time it takes to transport one snapshot goes to infinity. We consider a problem of broadcast communication in sensor networks, in which samples of a random field are collected at each node, and the goal is for all nodes to obtain an estimate of the entire field within a prescribed distortion value. The main idea we explore in this paper is that of jointly compressing the data generated by different nodes as this information travels over multiple hops, to eliminate correlations in the representation of the sampled field. Our main contributions are: (a) we obtain, using simple network flow concepts, conditions on the rate distortion function of the random field, so as to guarantee that any node can obtain the measurements collected at every other node in the network, quantized to within any prescribed distortion value; and (b) we construct a large class of physically-motivated stochastic models for sensor data, for which we are able to prove that the joint rate distortion function of all the data generated by the whole network grows slower than the bounds found in (a). A truly novel aspect of our work is the tight coupling between routing and source coding, explicitly formulated in a simple and analytically tractable model - to the best of our knowledge, this connection had not been studied before. In high-dimensional magnetic resonance imaging applications, time-consuming, sequential acquisition of data samples in the spatial frequency domain ( @math -space) can often be accelerated by accounting for dependencies in linear reconstruction, at the cost of noise amplification that depends on the sampling pattern. Common examples are support-constrained, parallel, and dynamic MRI, and @math -space sampling strategies are primarily driven by image-domain metrics that are expensive to compute for arbitrary sampling patterns. It remains challenging to provide systematic and computationally efficient automatic designs of arbitrary multidimensional Cartesian sampling patterns that mitigate noise amplification, given the subspace to which the object is confined. To address this problem, this paper introduces a theoretical framework that describes local geometric properties of the sampling pattern and relates them to the spread in the eigenvalues of the information matrix described by its first two spectral moments. This new criterion is then used for very efficient optimization of complex multidimensional sampling patterns that does not require reconstructing images or explicitly mapping noise amplification. Experiments with in vivo data show strong agreement between this criterion and traditional, comprehensive image-domain- and @math -space-based metrics, indicating the potential of the approach for computationally efficient (on-the-fly), automatic, and adaptive design of sampling patterns. We consider sensor networks that measure spatio-temporal correlated processes. An important task in such settings is the reconstruction at a certain node, called the sink, of the data at all points of the field. We consider scenarios where data is time critical, so delay results in distortion, or suboptimal estimation and control. For the reconstruction, the only data available to the sink are the values measured at the nodes of the sensor network, and knowledge of the correlation structure: this results in spatial distortion of reconstruction. Also, for the sake of power efficiency, sensor nodes need to transmit their data by relaying through the other network nodes: this results in delay, and thus temporal distortion of reconstruction if time critical data is concerned. We study data gathering for the case of Gaussian processes in one- and two-dimensional grid scenarios, where we are able to write explicit expressions for the spatial and time distortion, and combine them into a single total distortion measure. We prove that, for various standard correlation structures, there is an optimal finite density of the sensor network for which the total distortion is minimized. Thus, when power efficiency and delay are both considered in data gathering, it is useless from the point of view of accuracy of the reconstruction to increase the number of sensors above a certain threshold that depends on the correlation structure characteristics. We apply the theory of Markov random fields on trees to derive a phase transition in the number of samples needed in order to reconstruct phylogenies. We consider the Cavender-Farris-Neyman model of evolution on trees, where all the inner nodes have degree at least 3, and the net transition on each edge is bounded by e. Motivated by a conjecture by M. Steel, we show that if 2(1 - 2∈) 2 > 1, then for balanced trees, the topology of the underlying tree, having n leaves, can be reconstructed from O(logn) samples (characters) at the leaves. On the other hand, we show that if 2(1 - 2∈) 2 < 1, then there exist topologies which require at least n Ω(1) samples for reconstruction. Our results are the first rigorous results to establish the role of phase transitions for Markov random fields on trees, as studied in probability, statistical physics and information theory, for the study of phylogenies in mathematical biology. Sparsity in the Fourier domain is an important property that enables the dense reconstruction of signals, such as 4D light fields, from a small set of samples. The sparsity of natural spectra is often derived from continuous arguments, but reconstruction algorithms typically work in the discrete Fourier domain. These algorithms usually assume that sparsity derived from continuous principles will hold under discrete sampling. This article makes the critical observation that sparsity is much greater in the continuous Fourier spectrum than in the discrete spectrum. This difference is caused by a windowing effect. When we sample a signal over a finite window, we convolve its spectrum by an infinite sinc, which destroys much of the sparsity that was in the continuous domain. Based on this observation, we propose an approach to reconstruction that optimizes for sparsity in the continuous Fourier spectrum. We describe the theory behind our approach and discuss how it can be used to reduce sampling requirements and improve reconstruction quality. Finally, we demonstrate the power of our approach by showing how it can be applied to the task of recovering non-Lambertian light fields from a small number of 1D viewpoint trajectories. Let W be a correlated complex non-central Wishart matrix defined through W=X^HX, where X is an nxm(n>=m) complex Gaussian with non-zero mean @U and non-trivial covariance @S. We derive exact expressions for the cumulative distribution functions (c.d.f.s) of the extreme eigenvalues (i.e., maximum and minimum) of W for some particular cases. These results are quite simple, involving rapidly converging infinite series, and apply for the practically important case where @U has rank one. We also derive analogous results for a certain class of gamma-Wishart random matrices, for which @U^H@U follows a matrix-variate gamma distribution. The eigenvalue distributions in this paper have various applications to wireless communication systems, and arise in other fields such as econometrics, statistical physics, and multivariate statistics. We address the problem of deterministic oversampling of bandlimited sensor fields in a distributed communication-constrained processing environment, where it is desired for a central intelligent unit to reconstruct the sensor field to maximum pointwise accuracy.We show, using a dither-based sampling scheme, that is is possible to accomplish this using minimal inter-sensor communication with the aid of a multitude of low-precision sensors. Furthermore, we show the feasibility of having a flexible tradeoff between the average oversampling rate and the Analog to Digital (A D) quantization precision per sensor sample with respect to achieving exponential accuracy in the number of bits per Nyquist-period, thereby exposing a key underpinning "conservation of bits" principle. That is, we can distribute the bit budget per Nyquist-period along the amplitude-axis (precision of A D converter) and space (or time or space-time) using oversampling in an almost arbitrary discrete-valued manner, while retaining the same reconstruction error decay profile. Interestingly this oversampling is possible in a highly localized communication setting, with only nearest-neighbor communication, making it very attractive for dense sensor networks operating under stringent inter-node communication constraints. Finally we show how our scheme incorporates security as a by-product due to the presence of an underlying dither signal which can be used as a natural encryption device for security. The choice of the dither function enhances the security of the network. The generalized eigenvalue problem @math with H a Hankel matrix and @math the corresponding shifted Hankel matrix occurs in number of applications such as the reconstruction of the shape of a polygon from its moments, the determination of abscissa of quadrature formulas, of poles of Pade approximants, or of the unknown powers of a sparse black box polynomial in computer algebra. In many of these applications, the entries of the Hankel matrix are only known up to a certain precision. We study the sensitivity of the nonlinear application mapping the vector of Hankel entries to its generalized eigenvalues. A basic tool in this study is a result on the condition number of Vandermonde matrices with not necessarily real abscissas which are possibly row-scaled. Manhattan-world urban scenes are common in the real world. We propose a fully automatic approach for reconstructing such scenes from 3D point samples. Our key idea is to represent the geometry of the buildings in the scene using a set of well-aligned boxes. We first extract plane hypothesis from the points followed by an iterative refinement step. Then, candidate boxes are obtained by partitioning the space of the point cloud into a non-uniform grid. After that, we choose an optimal subset of the candidate boxes to approximate the geometry of the buildings. The contribution of our work is that we transform scene reconstruction into a labeling problem that is solved based on a novel Markov Random Field formulation. Unlike previous methods designed for particular types of input point clouds, our method can obtain faithful reconstructions from a variety of data sources. Experiments demonstrate that our method is superior to state-of-the-art methods. We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. As demonstrated heuristically and numerically by KrzakalaEtAl , message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements with undersampling rates close to the fraction of non-zero coordinates. We use an approximate message passing (AMP) algorithm and analyze it through the state evolution method. We give a rigorous proof that this approach is successful as soon as the undersampling rate @math exceeds the (upper) R 'enyi information dimension of the signal, @math . More precisely, for a sequence of signals of diverging dimension @math whose empirical distribution converges to @math , reconstruction is with high probability successful from @math measurements taken according to a band diagonal matrix. For sparse signals, i.e., sequences of dimension @math and @math non-zero entries, this implies reconstruction from @math measurements. For discrete' signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from @math measurements. The result is robust with respect to noise, does not apply uniquely to random signals, but requires the knowledge of the empirical distribution of the signal @math . Given samples from an unknown multivariate distribution @math , is it possible to distinguish whether @math is the product of its marginals versus @math being far from every product distribution? Similarly, is it possible to distinguish whether @math equals a given distribution @math versus @math and @math being far from each other? These problems of testing independence and goodness-of-fit have received enormous attention in statistics, information theory, and theoretical computer science, with sample-optimal algorithms known in several interesting regimes of parameters. Unfortunately, it has also been understood that these problems become intractable in large dimensions, necessitating exponential sample complexity. Motivated by the exponential lower bounds for general distributions as well as the ubiquity of Markov Random Fields (MRFs) in the modeling of high-dimensional distributions, we initiate the study of distribution testing on structured multivariate distributions, and in particular the prototypical example of MRFs: the Ising Model. We demonstrate that, in this structured setting, we can avoid the curse of dimensionality, obtaining sample and time efficient testers for independence and goodness-of-fit. One of the key technical challenges we face along the way is bounding the variance of functions of the Ising model. This paper presents a novel probabilistic foundation for volumetric 3D reconstruction. We formulate the problem as inference in a Markov random field, which accurately captures the dependencies between the occupancy and appearance of each voxel, given all input images. Our main contribution is an approximate highly parallelized discrete-continuous inference algorithm to compute the marginal distributions of each voxel's occupancy and appearance. In contrast to the MAP solution, marginals encode the underlying uncertainty and ambiguity in the reconstruction. Moreover, the proposed algorithm allows for a Bayes optimal prediction with respect to a natural reconstruction loss. We compare our method to two state-of-the-art volumetric reconstruction algorithms on three challenging aerial datasets with LIDAR ground truth. Our experiments demonstrate that the proposed algorithm compares favorably in terms of reconstruction accuracy and the ability to expose reconstruction uncertainty. In this paper, we present a general formulation that unifies the probabilistic characterization of Hermitian random matrices with a specific structure. Based on a general expression for the joint pdf of the ordered eigenvalues, we obtain i) the joint cdf; ii) the marginal cdfs; and iii) the marginal pdfs of the ordered eigenvalues, where ii) and iii) follow as simple particularizations of i). Our formulation is shown to include the distribution of some common MIMO channel models such as the uncorrelated, semicorrelated, and double-correlated Rayleigh MIMO fading channel and the uncorrelated Rician MIMO fading channel, although it is not restricted only to these. Hence, the proposed formulation and derived results provide a solid framework for the simultaneous analytical performance analysis of MIMO systems under different channel models. As an illustrative application, we obtain the exact outage probability of a spatial multiplexing MIMO system transmitting through the strongest channel eigenmodes. Light field microscopy is a new technique for high-speed volumetric imaging of weakly scattering or fluorescent specimens. It employs an array of microlenses to trade off spatial resolution against angular resolution, thereby allowing a 4-D light field to be captured using a single photographic exposure without the need for scanning. The recorded light field can then be used to computationally reconstruct a full volume. In this paper, we present an optical model for light field microscopy based on wave optics, instead of previously reported ray optics models. We also present a 3-D deconvolution method for light field microscopy that is able to reconstruct volumes at higher spatial resolution, and with better optical sectioning, than previously reported. To accomplish this, we take advantage of the dense spatio-angular sampling provided by a microlens array at axial positions away from the native object plane. This dense sampling permits us to decode aliasing present in the light field to reconstruct high-frequency information. We formulate our method as an inverse problem for reconstructing the 3-D volume, which we solve using a GPU-accelerated iterative algorithm. Theoretical limits on the depth-dependent lateral resolution of the reconstructed volumes are derived. We show that these limits are in good agreement with experimental results on a standard USAF 1951 resolution target. Finally, we present 3-D reconstructions of pollen grains that demonstrate the improvements in fidelity made possible by our method. Image-based or light field rendering has received much recent attention as an alternative to traditional geometric methods for modeling and rendering complex objects. A light field represents the radiance flowing through all the points in a scene in all possible directions. We explore two new techniques for efficiently acquiring, storing, and reconstructing light fields in a (nearly) uniform fashion. Both techniques sample the light field by sampling the set of lines that intersect a sphere tightly fit around a given object. Our first approach relies on uniformly subdividing the sphere and representing this subdivision in a compact data structure which allows efficient mapping of image pixels or rays to sphere points and then to subdivision elements. We sample a light field by joining pairs of subdivision elements and store the resulting samples in a multi-resolution, highly compressed fashion that allows efficient rendering. Our second method allows a uniform sampling of all five dimensions of the light field, using hierarchical subdivision for directional space and uniform grid sampling for positional space. Light field models are acquired using parallel projections along a set of uniform directions. Depth information can also be stored for high-quality image rendering. The system can provide bounds on key sources of error in the representation and can be generalized to arbitrary scenes comprising multiple complex objects. Abstract The problem of reconstructing a function f from a set of non-uniformly distributed, weighted-average sampled values ∫ R d f(x)ψ x j (x) d x: j∈J is studied in the context of shift-invariant subspaces of L 2 ( R d ) . Necessary density conditions on the sampling set X= x j : j∈J for stable reconstruction are obtained, and fast iterative algorithms are described. The performance of the algorithms are analyzed when the data are corrupted by noise. Estimates are derived for the convergence rates of the algorithms in terms of the sampling density and the diameters of the sampling functionals ψ x j : x j ∈X . The results provide a mathematical framework for situations arising frequently in applications, e.g., when the sample values are not precise because they are gathered by real-world acquisition devices.