Search

We study the recovery of operators with a bandlimited Kohn–Nirenberg symbol from the action of such operators on a weighted impulse train, a procedure we refer to as sampling of operators. Kailath, Bello, and later Kozek and the authors have shown that the sampling of operators is possible if the symbol of the operator is bandlimited to a set with area less than one. In this paper, we develop the theory of the sampling of operators in analogy with the classical theory of sampling of bandlimited functions. We define the notions of sampling set and sampling rate for operators and give necessary and sufficient conditions on the sampling rate that depend on the size and geometry of the bandlimiting set. We develop explicit reconstruction formulas for operator sampling that generalize reconstruction formulas for bandlimited functions. We give necessary and sufficient conditions on the bandlimiting set under which sampling of operators is possible by their action on a given periodically weighted delta train. We show that under mild geometric conditions on the bandlimiting set, classes of operators are bandlimited to an unknown set of area less than one-half permit sampling and reconstruction. We generalize two results of the Heckel and Bölcskei concerning sampling of operators with area not greater than one-half and less than one, respectively, by finding a larger class of operators to which they apply. Operators with bandlimited symbols have been used to model doubly dispersive communication channels with slowly time-varying impulse response. The results in this paper are rooted in work by Bello and Kailath in the 1960s. [ABSTRACT FROM PUBLISHER]

We consider Laurent polynomial (LP) matrices defined on the unit circle of the complex plane. QR decomposition of an LP matrix \bf A(s) yields QR factors \bf Q(s) and \bf R(s) that, in general, are neither LP nor rational matrices. In this paper, we present an invertible mapping that transforms \bf Q(s) and \bf R(s) into LP matrices. Furthermore, we show that, given QR factors of sufficiently many samples of \bf A(s), it is possible to obtain QR factors of additional samples of \bf A(s) through application of this mapping followed by interpolation and inversion of the mapping. The results of this paper find applications in the context of signal processing for multiple–input multiple–output (MIMO) wireless communication systems that employ orthogonal frequency-division multiplexing (OFDM). [ABSTRACT FROM PUBLISHER]

This paper starts with new aliasing-truncation error upper bounds in the sampling theorem for non-bandlimited stochastic signals. Then, it investigates Lp([0,T]) approximations of the sub-Gaussian random signals. Explicit truncation error upper bounds are established. The obtained rate of convergence provides a constructive algorithm for determining the sampling rate and the sample size in the truncated Whittaker-Kotel’nikov-Shannon expansions to ensure the approximation of the sub-Gaussian signals with given accuracy and reliability. Some numerical examples are presented. [ABSTRACT FROM AUTHOR]

The minimum energy, and, more generally, the minimum cost, to transmit one bit of information was recently derived for bursty communication when information is available infrequently at random times at the transmitter. Furthermore, it was shown that even if the receiver is constrained to sample only a fraction $\rho \in ~(0,1]$ of the channel outputs, there is no capacity penalty. That is, for any strictly positive sampling rate $\rho $ , the asynchronous capacity per unit cost is the same as under full sampling, i.e., when $\rho =1$ . Moreover, there is no penalty in terms of decoding delay. These results are asymptotic in nature, considering the limit as the number $B$ of bits to be transmitted tends to infinity, while the sampling rate $\rho $ remains fixed. A natural question is then whether the sampling rate $\rho (B)$ can drop to zero without introducing a capacity (or delay) penalty compared with full sampling. We answer this question affirmatively. The main result of this paper is an essentially tight characterization of the minimum sampling rate. We show that any sampling rate that grows at least as fast as $\omega (1/B)$ is achievable, while any sampling rate smaller than $o(1/B)$ yields unreliable communication. The key ingredient in our improved achievability result is a new, multi-phase adaptive sampling scheme for locating transient changes, which we believe may be of independent interest for certain change-point detection problems. [ABSTRACT FROM PUBLISHER]

Despite its reduced complexity, lattice reduction-aided decoding exhibits a widening gap to maximum-likelihood (ML) performance as the dimension increases. To improve its performance, this paper presents randomized lattice decoding based on Klein's sampling technique, which is a randomized version of Babai's nearest plane algorithm [i.e., successive interference cancelation (SIC)] and samples lattice points from a Gaussian-like distribution over the lattice. To find the closest lattice point, Klein's algorithm is used to sample some lattice points and the closest among those samples is chosen. Lattice reduction increases the probability of finding the closest lattice point, and only needs to be run once during preprocessing. Further, the sampling can operate very efficiently in parallel. The technical contribution of this paper is twofold: we analyze and optimize the decoding radius of sampling decoding resulting in better error performance than Klein's original algorithm, and propose a very efficient implementation of random rounding. Of particular interest is that a fixed gain in the decoding radius compared to Babai's decoding can be achieved at polynomial complexity. The proposed decoder is useful for moderate dimensions where sphere decoding becomes computationally intensive, while lattice reduction-aided decoding starts to suffer considerable loss. Simulation results demonstrate near-ML performance is achieved by a moderate number of samples, even if the dimension is as high as 32. [ABSTRACT FROM AUTHOR]

This paper considers the problem of estimating a stationary sequence \bf y from the observation of a stationary correlated sequence \bf x by means of a causal linear filter. Thereby, it is assumed that the spectral density \Phi{\bf x} of \bf x vanishes on a subset of the unit circle of positive Lebesgue measure such that the classical derivation of the estimation filter, based on the spectral factorization of \Phi{\bf x}, can not be applied. The paper derives the transfer function of such an estimation filter, discusses its stability behavior, and applies the result to the causal reconstruction of deterministic signals from its samples. [ABSTRACT FROM PUBLISHER]

In the matter of selection of sample time points for the estimation of the power spectral density of a continuous time stationary stochastic process, irregular sampling schemes such as Poisson sampling are often preferred over regular (uniform) sampling. A major reason for this preference is the well-known problem of inconsistency of estimators based on regular sampling, when the underlying power spectral density is not bandlimited. It is argued in this paper that, in consideration of a large sample property like consistency, it is natural to allow the sampling rate to go to infinity as the sample size goes to infinity. Through appropriate asymptotic calculations under this scenario, it is shown that the smoothed periodogram based on regularly spaced data is a consistent estimator of the spectral density, even when the latter is not band-limited. It transpires that, under similar assumptions, the estimators based on uniformly sampled and Poisson-sampled data have about the same rate of convergence. Apart from providing this reassuring message, the paper also gives a guideline for practitioners regarding appropriate choice of the sampling rate. Theoretical calculations for large samples and Monte-Carlo simulations for small samples indicate that the smoothed periodogram based on uniformly sampled data have less variance and more bias than its counterpart based on Poisson sampled data. [ABSTRACT FROM AUTHOR]

By considering elliptical correlations in the channel matrix of a large MIMO system, this paper investigates how the non-linear dependency affects the asymptotic behaviors of Shannon’s mutual information, as the numbers of antennas at transmitter and receiver both tend to infinity at the same rate. Beyond the almost sure convergence of the information per transmit antenna, we also propose several central limit theorems for the information statistics under various scenarios. The results show that the non-linear correlation has a little impact on the almost sure convergence but has a tremendous effect on the fluctuation of the information statistics. In particular, the centralized information statistics could experience a phase transition in convergence rate when the strength of the non-linear correlation increases. As extensions, several central limit theorems are established as well for general linear spectral statistics of large sample covariance matrices in elliptical distributions. [ABSTRACT FROM AUTHOR]

This paper investigates the effect of sub-Nyquist sampling upon the capacity of an analog channel. The channel is assumed to be a linear time-invariant Gaussian channel, where perfect channel knowledge is available at both the transmitter and the receiver. We consider a general class of right-invertible time-preserving sampling methods which includes irregular nonuniform sampling, and characterize in closed form the channel capacity achievable by this class of sampling methods, under a sampling rate and power constraint. Our results indicate that the optimal sampling structures extract out the set of frequencies that exhibits the highest signal-to-noise ratio among all spectral sets of measure equal to the sampling rate. This can be attained through filterbank sampling with uniform sampling grid employed at each branch with possibly different rates, or through a single branch of modulation and filtering followed by uniform sampling. These results reveal that for a large class of channels, employing irregular nonuniform sampling sets, while are typically complicated to realize in practice, does not provide capacity gain over uniform sampling sets with appropriate preprocessing. Our findings demonstrate that aliasing or scrambling of spectral components does not provide capacity gain in this scenario, which is in contrast to the benefits obtained from random mixing in spectrum-blind compressive sampling schemes. [ABSTRACT FROM PUBLISHER]

This paper studies the sample complexity of searching over multiple populations. We consider a large number of populations, each corresponding to either distribution P0 or P1. The goal of the search problem studied here is to find one population corresponding to distribution P1 with as few samples as possible. The main contribution is to quantify the number of samples needed to correctly find one such population. We consider two general approaches: nonadaptive sampling methods, which sample each population a predetermined number of times until a population following P1 is found, and adaptive sampling methods, which employ sequential sampling schemes for each population. We first derive a lower bound on the number of samples required by any sampling scheme. We then consider an adaptive procedure consisting of a series of sequential probability ratio tests, and show it comes within a constant factor of the lower bound. We give explicit expressions for this constant when samples of the populations follow Gaussian and Bernoulli distributions. An alternative adaptive scheme is discussed which does not require full knowledge of P1, and comes within a constant factor of the optimal scheme. For comparison, a lower bound on the sampling requirements of any nonadaptive scheme is presented. [ABSTRACT FROM AUTHOR]

We propose robust and efficient algorithms for the joint sparse recovery problem in compressed sensing, which simultaneously recover the supports of jointly sparse signals from their multiple measurement vectors obtained through a common sensing matrix. In a favorable situation, the unknown matrix, which consists of the jointly sparse signals, has linearly independent nonzero rows. In this case, the MUltiple SIgnal Classification (MUSIC) algorithm, originally proposed by Schmidt for the direction of arrival estimation problem in sensor array processing and later proposed and analyzed for joint sparse recovery by Feng and Bresler, provides a guarantee with the minimum number of measurements. We focus instead on the unfavorable but practically significant case of rank defect or ill-conditioning. This situation arises with a limited number of measurement vectors, or with highly correlated signal components. In this case, MUSIC fails and, in practice, none of the existing methods can consistently approach the fundamental limit. We propose subspace-augmented MUSIC (SA-MUSIC), which improves on MUSIC such that the support is reliably recovered under such unfavorable conditions. Combined with a subspace-based greedy algorithm, known as Orthogonal Subspace Matching Pursuit, which is also proposed and analyzed in this paper, SA-MUSIC provides a computationally efficient algorithm with a performance guarantee. The performance guarantees are given in terms of a version of the restricted isometry property. In particular, we also present a non-asymptotic perturbation analysis of the signal subspace estimation step, which has been missing in the previous studies of MUSIC. [ABSTRACT FROM PUBLISHER]

Scalar quantization is the most practical and straightforward approach to signal quantization. However, it has been shown that scalar quantization of oversampled or compressively sensed signals can be inefficient in terms of the rate-distortion tradeoff, especially as the oversampling rate or the sparsity of the signal increases. In this paper, we modify the scalar quantizer to have discontinuous quantization regions. We demonstrate that with this modification it is possible to achieve exponential decay of the quantization error as a function of the oversampling rate instead of the quadratic decay exhibited by current approaches. Our approach is universal in the sense that prior knowledge of the signal model is not necessary in the quantizer design, only in the reconstruction. Thus, we demonstrate that it is possible to reduce the quantization error by incorporating side information on the acquired signal, such as sparse signal models or signal similarity with known signals. In doing so, we establish a relationship between quantization performance and the Kolmogorov entropy of the signal model. [ABSTRACT FROM AUTHOR]

Traffic with self-similar and heavy-tailed characteristics has been widely reported in communication networks, yet, the state-of-the-art of analytically predicting the delay performance of such networks is lacking. This work addresses heavy-tailed traffic that has a finite first moment, but no second moment, and presents end-to-end delay bounds for such traffic. The derived performance bounds are non-asymptotic in that they do not assume a steady state, large buffer, or many sources regime. The analysis follows a network calculus approach where traffic is characterized by envelope functions and service is described by service curves. The system model is a multi-hop path of fixed-capacity links with heavy-tailed self-similar cross traffic at each node. A key contribution of the paper is a probabilistic sample-path bound for heavy-tailed arrival and service processes, which is based on a scale-free sampling method. The paper explores how delay bounds scale as a function of the length of the path, and compares them with lower bounds. A comparison with simulations illustrates pitfalls when simulating self-similar heavy-tailed traffic, providing further evidence for the need of analytical bounds. [ABSTRACT FROM AUTHOR]

Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L_1-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L_1-distance \Vert p-q\Vert _1 can be estimated with a constant precision using only O(N^1/2) queries in the quantum settings, whereas classical computers need \Omega(N^1-o(1)) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N^1/3). The classical query complexity of these problems is known to be \Omega(N^1/2). [ABSTRACT FROM AUTHOR]

In this paper, the convergence behavior of the symmetric and the nonsymmetric Shannon sampling series is analyzed for bandlimited continuous-time wide-sense stationary stochastic processes that have absolutely continuous spectral measure. It is shown that the nonsymmetric sampling series converges in the mean-square sense uniformly on compact subsets of the real axis if and only if the power spectral density of the process fulfills a certain integrability condition. Moreover, if this condition is not fulfilled, then the pointwise mean-square approximation error of the nonsymmetric sampling series and the supremum of the mean-square approximation error over the real axis of the symmetric sampling series both diverge. This shows that there is a significant difference between the convergence behavior of the symmetric and the nonsymmetric sampling series. [ABSTRACT FROM PUBLISHER]

There are several reasons why the classical sampling theorem is rather impractical for real life signal processing. First, the sine-kernel is not very suitable for fast and efficient computation; it decays much too slowly. Second, in practice only a finite number N of sampled values are available, so that the representation of a signal f by the finite sum would entail a truncation error which decreases rather slowly for N → ∞, due to the first drawback. Third, band-limitation is a definite restriction, due to the nonconformity of band and time-limited signals. Further, the samples needed extend from the entire past to the full future, relative to some time t = to. This paper presents an approach to overcome these difficulties. The sine-function is replaced by certain simple linear combinations of shifted B-splines, only a.finite number of samples from the past need be available. This deterministic approach can be used to process arbitrary, not necessarily bandlimited nor differentiable signals, and even not necessarily continuous signals. Best possible error estimates in terms of an Lp-average modulus of smoothness are presented. Several typical examples exhibiting the various problems involved are worked out in detail. [ABSTRACT FROM AUTHOR]

Traditional sampling theories consider the problem of reconstructing an unknown signal x from a series of samples. A prevalent assumption which often guarantees recovery from the given measurements is that x lies in a known subspace. Recently, there has been growing interest in nonlinear but structured signal models, in which x lies in a union of subspaces. In this paper, we develop a general framework for robust and efficient recovery of such signals from a given set of samples. More specifically, we treat the case in which x lies in a sum of k subspaces, chosen from a larger set of m possibilities. The samples are modeled as inner products with an arbitrary set of sampling functions. To derive an efficient and robust recovery algorithm, we show that our problem can be formulated as that of recovering a block-sparse vector whose nonzero elements appear in fixed blocks. We then propose a mixed l2/l1 program for block sparse recovery. Our main result is an equivalence condition under which the proposed convex algorithm is guaranteed to recover the original signal. This result relies on the notion of block restricted isometry property (RIP), which is a generalization of the standard RIP used extensively in the context of compressed sensing. Based on RIP, we also prove stability of our approach in the presence of noise and modeling errors. A special case of our framework is that of recovering multiple measurement vectors (MMV) that share a joint sparsity pattern. Adapting our results to this context leads to new MMV recovery methods as well as equivalence conditions under which the entire set can be determined efficiently. [ABSTRACT FROM AUTHOR]

The discovery of networks is a fundamental problem arising in numerous fields of science and technology, including communication systems, biology, sociology, and neuroscience. Unfortunately, it is often difficult, or impossible, to obtain data that directly reveal network structure, and so one must infer a network from incomplete data. This paper considers inferring network structure from "co-occurrence" data: observations that identify which network components (e.g., switches, routers, genes) carry each transmission but do not indicate the order in which they handle the transmission. Without order information, the number of networks that are consistent with the data grows exponentially with the size of the network (i.e., the number of nodes). Yet, the basic engineering/evolutionary principles underlying most networks strongly suggest that not all data-consistent networks are equally likely. In particular, nodes that co-occur in many observations are probably closely connected. With this in mind, we model the co-occurrence observations as independent realizations of a random walk on the network, subjected to a random permutation to account for the lack of order information. Treating permutations as missing data, we derive an expectation-maximization (EM) algorithm for estimating the random walk parameters. The model and EM algorithm significantly simplify the problem, but the computational complexity of the reconstruction process does grow exponentially in the length of each transmission path. For networks with long paths, the exact E-step may be computationally intractable. We propose a polynomial-time Monte Carlo EM algorithm based on importance sampling and derive conditions that ensure convergence of the algorithm with high probability. Simulations and experiments with Internet measurements demonstrate the promise of this approach. [ABSTRACT FROM AUTHOR]

The paper examines the impact of the additive correlated noise on the accuracy of the signal reconstruction algorithm originating from the Whittaker-Shannon (WS) sampling interpolation formula. A class of band-limited signals as well as signals which are non-band-limited are taken into consideration. The pro- posed reconstruction method is a smooth post-filtering correction of the classical WS interpolation series. We assess both the point- wise and global accuracy of the proposed reconstruction algorithm for a broad class of dependent noise processes. This includes short and long-memory stationary errors being independent of the sampling rate. We also examine a class of noise processes for which the correlation function depends on the sampling rate. Whereas the short-memory errors have relatively small influence on the reconstruction accuracy, the long-memory errors can greatly slow down the convergence rate. In the case of the noise model depending on the sampling rate further degradation of the algorithm accuracy is observed. We give quantitative explanations of these phenomena by deriving rates at which the reconstruction error tends to zero. We argue that the obtained rates are close to be optimal. In fact, in a number of special cases they agree with known optimal mm-max rates. The problem of the limit distribution of the L2 distance of the proposed reconstruction algorithm is also addressed. This result allows us to tackle an important problem of designing non-parametric lack-of-fit tests. The theory of the asymptotic behavior of quadratic forms of stationary sequences is utilized in this case. [ABSTRACT FROM AUTHOR]

This paper considers online classification learning algorithms based on regularization schemes in reproducing kernel Hilbert spaces associated with general convex loss functions. A novel capacity independent approach is presented. It verifies the strong convergence of the algorithm under a very weak assumption of the step sizes and yields satisfactory convergence rates for polynomially decaying step sizes. Explicit learning rates with respect to the misclassification error are given in terms of the choice of step sizes and the regularization parameter (depending on the sample size). Error bounds associated with the hinge loss, the least square loss, and the support vector machine q-norm loss are presented to illustrate our method. [ABSTRACT FROM AUTHOR]

Motivated by sensor networks and other distributed settings, several models for distributed learning are presented. The models differ from classical works in statistical pattern recognition by allocating observations of an independent and identically distributed (i.i.d.) sampling process among members of a network of simple learning agents. The agents are limited in their ability to communicate to a central fusion center and thus, the amount of information available for use in classification or regression is constrained. For several basic communication models in both the binary classification and regression frameworks, we question the existence of agent decision rules and fusion rules that result in a universally consistent ensemble; the answers to this question present new issues to consider with regard to universal consistency. This paper addresses the issue of whether or not the guarantees provided by Stone's theorem in centralized environments hold in distributed settings. [ABSTRACT FROM AUTHOR]

The sampling theorem says that every band-limited signal is uniquely determined by its sampled values provided the sampling points satisfy certain conditions. However, sampled values obtained in practice may not be the exact values of a signal at sampling points, but only averages of the signal near these points. Gröchenig proved that band-limited signals can be reconstructed exactly from local averages if the sampling density is large enough. In this paper, we study the reconstruction of band-limited signals from local averages with symmetric averaging functions. We study the aliasing error arising when a non-band-limited signal is reconstructed from local averages and give explicit error bounds. Since the classical "point sampling" can be viewed as a limiting case of average sampling, we indeed give new aliasing error bounds for both regular and irregular sampling. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of estimating finite rate of innovation (FRI) signals from noisy measurements, and specifically analyze the interaction between FRI techniques and the underlying sampling methods. We first obtain a fundamental limit on the estimation accuracy attainable regardless of the sampling method. Next, we provide a bound on the performance achievable using any specific sampling approach. Essential differences between the noisy and noise-free cases arise from this analysis. In particular, we identify settings in which noise-free recovery techniques deteriorate substantially under slight noise levels, thus quantifying the numerical instability inherent in such methods. This instability, which is only present in some families of FRI signals, is shown to be related to a specific type of structure, which can be characterized by viewing the signal model as a union of subspaces. Finally, we develop a methodology for choosing the optimal sampling kernels for linear reconstruction, based on a generalization of the Karhunen–Loève transform. The results are illustrated for several types of time-delay estimation problems. [ABSTRACT FROM PUBLISHER]

A practical constraint that comes in the way of spectrum estimation of a continuous time stationary stochastic process is the minimum separation between successively observed samples of the process. When the underlying process is not band-limited, sampling at any uniform rate leads to aliasing, while certain stochastic sampling schemes, including Poisson process sampling, are rendered infeasible by the constraint of minimum separation. It is shown in this paper that, subject to this constraint, no point process sampling scheme is alias-free for the class of all spectra. It turns out that point process sampling under this constraint can be alias-free for band-limited spectra. However, the usual construction of a consistent spectrum estimator does not work in such a case. Simulations indicate that a commonly used estimator, which is consistent in the absence of this constraint, performs poorly when the constraint is present. These results should help practitioners in rationalizing their expectations from point process sampling as far as spectrum estimation is concerned, and motivate researchers to look for appropriate estimators of bandlimited spectra. [ABSTRACT FROM AUTHOR]

In this paper, we study the question of the representation of random variables by means of frames or Riesz basis generated by stationary sequences. This concerns the representation of continuous time wide sense stationary random processes by means of discrete samples. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment p (BPDQ_p), that model the quantization distortion more faithfully than the commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by minimizing the sparsity of the signal to be reconstructed subject to a data-fidelity constraint expressed in the \ell_p-norm of the residual error for 2\leqslant p\leqslant \infty. [ABSTRACT FROM AUTHOR]

This paper treats the problem of learning a dictionary providing sparse representations for a given signal class, via ℓ1-minimization. The problem can also be seen as factorizing a d x N matrix Y = (y1 ... yN), yn ∈ ℝd of training signals into a d x K dictionary matrix φ and a K x N coefficient matrix X = (x1 ... xN),xn ∈ ℝK, which is sparse. The exact question studied here is when a dictionary coefficient pair (φ, X) can be recovered as local minimum of a (nonconvex) ℓ1-criterion with input Y = φ X. First, for general dictionaries and coefficient matrices, algebraic conditions ensuring local identifiability are derived, which are then specialized to the case when the dictionary is a basis. Finally, assuming a random Bernoulli-Gaussian sparse model on the coefficient matrix, it is shown that sufficiently incoherent bases are locally identifiable with high probability. The perhaps surprising result is that the typically sufficient number of training samples N grows up to a logarithmic factor only linearly with the signal dimension, i.e., N ≈ CK log K, in contrast to previous approaches requiring combinatorially many samples. [ABSTRACT FROM AUTHOR]

This paper considers basic questions regarding Markov random processes. It shows that continuous-time, continuous-valued, wide-sense stationary, Markov processes that have absolutely continuous second-order distribution and finite second moment are not bandlimited. It also shows that continuous-time, stationary, Markov processes that are continuous-valued or discrete-valued and satisfy additional mild conditions cannot be recovered from uniform sampling. Further it shows that continuous-time, continuous-valued, stationary, Markov processes that have absolutely continuous second-order distributions and are continuous almost surely, cannot be recovered without error after quantization. Finally, it provides necessary and sufficient conditions for stationary, discrete-time, Markov processes to have zero entropy rate, and relates this to information singularity. [ABSTRACT FROM AUTHOR]

Recently, it has been observed that a sparse trigonometric polynomial, i.e., having only a small number of nonzero coefficients, can be reconstructed exactly from a small number of random samples using basis pursuit (BP) or orthogonal matching pursuit (OMP). In this paper, it is shown that recovery by a BP variant is stable under perturbation of the samples values by noise. A similar partial result for OMP is provided. For BP, in addition, the stability result is extended to (nonsparse) trigonometric polynomials that can be well approximated by sparse ones. The theoretical findings are illustrated by numerical experiments. [ABSTRACT FROM AUTHOR]

One problem with active measurement is that, while it is suitable for measuring time-average network performance, it is difficult to measure per-flow quality of service (QoS), which is defined as the average over packets in the flow. To achieve such per-flow QoS measurement, the authors proposed a new technique, called the change-of- measure-based passive/active monitoring (CoMPACT Monitor), which is based on the change-of-measure framework in probability/measure theory and transforms actively obtained information by using passively monitored data. This technique enables us to concurrently measure one-way delay information about individual users, applications, and organizations in detail in a lightweight manner. This paper presents the mathematical formulation for the CoMPACT Monitor and verifies that it works well under some weak conditions. In addition, we investigate its characteristics regarding several implementation issues through simulation and actual network experiments. The results reveal that our technique provides highly qualified estimates involving only a limited amount of extra traffic from active probes. [ABSTRACT FROM AUTHOR]

In this paper, we present a new class of importance sampling simulation distributions, the universal, distributions. We show that these distributions are universally efficient in the sense that they depend only on a single scalar parameter regardless of the dimensionality of the underlying system or of the error sets to be simulated. [ABSTRACT FROM AUTHOR]

We consider the canonical shared link caching network formed by a source node, hosting a library of $m$ information messages (files), connected via a noiseless multicast link to $n$ user nodes, each equipped with a cache of size $M$ files. Users request files independently at random according to an a-priori known demand distribution q. A coding scheme for this network consists of two phases: cache placement and delivery. The cache placement is a mapping of the library files onto the user caches that can be optimized as a function of the demand statistics, but is agnostic of the actual demand realization. After the user demands are revealed, during the delivery phase the source sends a codeword (function of the library files, cache placement, and demands) to the users, such that each user retrieves its requested file with arbitrarily high probability. The goal is to minimize the average transmission length of the delivery phase, referred to as rate (expressed in channel symbols per file). In the case of deterministic demands, the optimal min-max rate has been characterized within a constant multiplicative factor, independent of the network parameters. The case of random demands was previously addressed by applying the order-optimal min-max scheme separately within groups of files requested with similar probability. However, no complete characterization of order-optimality was previously provided for random demands under the average rate performance criterion. In this paper, we consider the random demand setting and, for the special yet relevant case of a Zipf demand distribution, we provide a comprehensive characterization of the order-optimal rate for all regimes of the system parameters, as well as an explicit placement and delivery scheme achieving order-optimal rates. We present also numerical results that confirm the superiority of our scheme with respect to previously proposed schemes for the same setting. [ABSTRACT FROM AUTHOR]

This paper considers the sequential composite hypothesis test with multiple sensors. The sensors observe random samples in parallel and communicate with a fusion center, who makes the global decision based on the sensor inputs. On the one hand, in the centralized scenario, where local samples are precisely transmitted to the fusion center, the generalized sequential likelihood ratio test (GSPRT) is shown to be asymptotically optimal in terms of the expected sample size as error rates tend to zero. On the other hand, for systems with limited power and bandwidth resources, decentralized solutions that only send a summary of local samples (we particularly focus on a one-bit communication protocol) to the fusion center is of great importance. To this end, we first consider a decentralized scheme where sensors send their one-bit quantized statistics every fixed period of time to the fusion center. We show that such a uniform sampling and quantization scheme is strictly suboptimal and its suboptimality can be quantified by the KL divergence of the distributions of the quantized statistics under both the hypotheses. We then propose a decentralized GSPRT based on level-triggered sampling. That is, each sensor runs its own GSPRT repeatedly and reports its local decision to the fusion center asynchronously. We show that this scheme is asymptotically optimal as the local thresholds and global thresholds grow large at different rates. Finally, two particular models and their associated applications are studied to compare the centralized and decentralized approaches. Numerical results are provided to demonstrate that the proposed level-triggered sampling based decentralized scheme aligns closely with the centralized scheme with substantially lower communication overhead, and significantly outperforms the uniform sampling and quantization-based decentralized scheme. [ABSTRACT FROM AUTHOR]

We consider the problem of constructing a linear map from a Hilbert space \mathcal H (possibly infinite dimensional) to \mathbb R^m that satisfies a restricted isometry property (RIP) on an arbitrary signal model, i.e., a subset of \mathcal H . We present a generic framework that handles a large class of low-dimensional subsets but also unstructured and structured linear maps. We provide a simple recipe to prove that a random linear map satisfies a general RIP with high probability. We also describe a generic technique to construct linear maps that satisfy the RIP. Finally, we detail how to use our results in several examples, which allow us to recover and extend many known compressive sampling results. [ABSTRACT FROM PUBLISHER]

Consider a discrete memoryless multiple source with $m$ components of which $k \leq m$ possibly different sources are sampled at each time instant and jointly compressed in order to reconstruct all the $m$ sources under a given distortion criterion. A new notion of sampling rate distortion function is introduced, and is characterized first for the case of fixed-set sampling. Next, for independent random sampling performed without knowledge of the source outputs, it is shown that the sampling rate distortion function is the same regardless of whether or not the decoder is informed of the sequence of sampled sets. Furthermore, memoryless random sampling is considered with the sampler depending on the source outputs and with an informed decoder. It is shown that deterministic sampling, characterized by a conditional point-mass, is optimal and suffices to achieve the sampling rate distortion function. For memoryless random sampling with an uninformed decoder, an upper bound for the sampling rate distortion function is seen to possess a similar property of conditional point-mass optimality. It is shown by example that memoryless sampling with an informed decoder can outperform strictly any independent random sampler, and that memoryless sampling can do strictly better with an informed decoder than without. [ABSTRACT FROM PUBLISHER]

We consider two theorems from the theory of compressive sensing. Mainly a theorem concerning uniform recovery of random sampling matrices, where the number of samples needed in order to recover an s-sparse signal from linear measurements (with high probability) is known to be m~\gtrsim~s(\ln s)^3\ln N. We present new and improved constants together with what we consider to be a more explicit proof. A proof that also allows for a slightly larger class of m\times N-matrices, by considering what is called effective sparsity. We also present a condition on the so-called restricted isometry constants, \deltas, ensuring sparse recovery via \ell^1-minimization. We show that \delta2s<4/\sqrt{41} is sufficient and that this can be improved further to almost allow for a sufficient condition of the type \delta2s<2/3. [ABSTRACT FROM AUTHOR]

Compressed sensing is a sampling technique which provides a fundamentally new approach to data acquisition. Comparing with traditional methods, compressed sensing makes full use of sparsity so that a sparse signal can be reconstructed from very few measurements. A central problem in compressed sensing is the construction of sensing matrices. While random sensing matrices have been studied intensively, only a few deterministic constructions are known. Inspired by algebraic geometry codes, we introduce a new deterministic construction via algebraic curves over finite fields, which is a natural generalization of DeVore's construction using polynomials over finite fields. The diversity of algebraic curves provides numerous choices for sensing matrices. By choosing appropriate curves, we are able to construct binary sensing matrices which are superior to Devore's ones. We hope this connection between algebraic geometry and compressed sensing will provide a new point of view and stimulate further research in both areas. [ABSTRACT FROM PUBLISHER]

We observe (X_i,Y_i)i=1^n where the Y_i's are real valued outputs and the X_i's are m\times T matrices. We observe a new entry X and we want to predict the output Y associated with it. We focus on the high-dimensional setting, where m T \gg n. This includes the matrix completion problem with noise, as well as other problems. We consider linear prediction procedures based on different penalizations, involving a mixture of several norms: the nuclear norm, the Frobenius norm and the \ell_1-norm. For these procedures, we prove sharp oracle inequalities, using a statistical learning theory point of view. A surprising fact in our results is that the rates of convergence do not depend on m and T directly. The analysis is conducted without the usually considered incoherency condition on the unknown matrix or restricted isometry condition on the sampling operator. Moreover, our results are the first to give for this problem an analysis of penalization (such as nuclear norm penalization) as a regularization algorithm: our oracle inequalities prove that these procedures have a prediction accuracy close to the deterministic oracle one, given that the reguralization parameters are well-chosen. [ABSTRACT FROM AUTHOR]

Adaptive sampling results in significant improvements in the recovery of sparse signals in white Gaussian noise. A sequential adaptive sampling-and-refinement procedure called Distilled Sensing (DS) is proposed and analyzed. DS is a form of multistage experimental design and testing. Because of the adaptive nature of the data collection, DS can detect and localize far weaker signals than possible from non-adaptive measurements. In particular, reliable detection and localization (support estimation) using non-adaptive samples is possible only if the signal amplitudes grow logarithmically with the problem dimension. Here it is shown that using adaptive sampling, reliable detection is possible provided the amplitude exceeds a constant, and localization is possible when the amplitude exceeds any arbitrarily slowly growing function of the dimension. [ABSTRACT FROM AUTHOR]

In "Counting faces of randomly projected polytopes when the projection radically lowers dimension" the authors proved an asymptotic sampling theorem for sparse signals, showing that n random measurements permit to reconstruct an N-vector having k nonzeros provided n > 2 · k · log(N/n)(1 + o(1)) reconstruction uses ℓ1 minimization. They also proved an asymptotic rate theorem, showing existence of real error-correcting codes for messages of length N which can correct all possible k-element error patterns using just n generalized checksum bits, where n > 2e · k log(N/n)(1 + o(1)) decoding uses ℓ1 minimization. Both results require an asymptotic framework, with N growing large. For applications, on the other hand, we are concerned with specific triples k, n, N. We exhibit triples (k, n, N) for which Compressed Sensing Matrices and Real Error-Correcting Codes surely exist and can be obtained with high probability by random sampling. These derive from exponential bounds on the probability of drawing 'bad' matrices. The bounds give conditions effective at finite-N, and converging to the known sharp asymptotic conditions for large N. Compared to other finite-N bounds known to us, they are much stronger, and much more explicit. Our bounds derive from asymptotics in "Counting faces of randomly projected polytopes when the projection radically lowers dimension" counting the expected number of k-dimensional faces of the randomly projected simplex TN-1 and cross-polytope CN.We develop here finite-N bounds on the expected discrepancy between the number of k-faces of the projected polytope AQ and its generator Q, for Q = TN-1 and cross-polytope. Our bounds also imply existence of interesting geometric objects. Thus, we exhibit triples (k, n, N) for which polytopes with 2N vertices can be centrally k-neighborly. [ABSTRACT FROM AUTHOR]

Analytical methods for finding moments of random Vandermonde matrices with entries on the unit circle are developed. Vandermonde Matrices play an important role in signal processing and wireless applications such as direction of arrival estimation, precoding, and sparse sampling theory, just to name a few. Within this framework, we extend classical freeness results on random matrices with independent and identically distributed (i.i.d.) entries and show that Vandermonde structured matrices can be treated in the same vein with different tools. We focus on various types of matrices, such as Vandermonde matrices with and without uniform phase distributions, as well as generalized Vandermonde matrices. In each case, we provide explicit expressions of the moments of the associated Gram matrix, as well as more advanced models involving the Vandermonde matrix. Comparisons with classical i.i.d, random matrix theory are provided, and deconvolution results are discussed. We review some applications of the results to the fields of signal processing and wireless communications. [ABSTRACT FROM AUTHOR]

The minimum distance of some families of expander codes is studied, as well as some related families of codes defined on bipartite graphs. The weight spectrum and the minimum distance of a random ensemble of such codes are computed and it is shown that it sometimes meets the Gilbert-Varshamov (GV) bound. A lower bound on the minimum distances of constructive families of expander codes is derived. The relative minimum distance of the expander code is shown to exceed the product bound, i.e., the quantity δ0δ1 where δ0 and δ1 are the minimum relative distances of the constituent codes. As a consequence of this, a polynomially constructible family of expander codes is obtained whose relative distance exceeds the Zyablov bound on the distance of serial concatenations. [ABSTRACT FROM AUTHOR]

In our “big data” age, the size and complexity of data is steadily increasing. Methods for dimension reduction are ever more popular and useful. Two distinct types of dimension reduction are “data-oblivious” methods such as random projections and sketching, and “data-aware” methods such as principal component analysis (PCA). Both have their strengths, such as speed for random projections, and data-adaptivity for PCA. In this work, we study how to combine them to get the best of both. We study “sketch and solve” methods that take a random projection (or sketch) first, and compute PCA after. We compute the performance of several popular sketching methods (random iid projections, random sampling, subsampled Hadamard transform, CountSketch, etc) in a general “signal-plus-noise” (or spiked) data model. Compared to well-known works, our results are: 1) give asymptotically exact results; 2) apply when the signal components are only slightly above the noise, but the projection dimension is non-negligible. We also study stronger signals allowing more general covariance structures. We find that: 1) signal strength decreases under projection in a delicate way depending on the structure of the data and the sketching method; 2) orthogonal projections are slightly more accurate; 3) randomization does not hurt too much, due to concentration of measure; 4) the CountSketch can be somewhat improved by a normalization method. Our results have implications for statistical learning and data analysis. We also illustrate that the results are highly accurate in simulations and in analyzing empirical data. [ABSTRACT FROM AUTHOR]

Examines the problem of periodic nonuniform sampling of a multiband signal and its reconstruction below the Nyquist rates. Overview on multicoset sampling; Algorithm used in the reconstruction problem; Discussion on error bounds computation; Conclusion.

We study the problem of interpolating all values of a discrete signal f of length N when d < N values are known, especially in the case when the Fourier transform of the signal is zero outside some prescribed index set \cal J; these comprise the (generalized) bandlimited spaces \BBB^\cal J. The sampling pattern for f is specified by an index set \cal I, and is said to be a universal sampling set if samples in the locations \cal I can be used to interpolate signals from \BBB^\cal J for any \cal J. When N is a prime power we give several characterizations of universal sampling sets, some structure theorems for such sets, an algorithm for their construction, and a formula that counts them. There are also natural applications to additive uncertainty principles. [ABSTRACT FROM PUBLISHER]

The flow size distribution is a useful metric for traffic modeling and management. Its estimation based on sampled data, however, is problematic. Previous work has shown that flow sampling (FS) offers enormous statistical benefits over packet sampling but high resource requirements precludes its use in routers. We present dual sampling (DS), a two-parameter family, which, to a large extent, provide FS-like statistical performance by approaching FS continuously, with just packet-sampling-like computational cost. Our work utilizes a Fisher information based approach recently used to evaluate a number of sampling schemes, excluding FS, for TCP flows. We revise and extend the approach to make rigorous and fair comparisons between FS, DS, and others. We show how DS significantly outperforms other packet based methods, including Sample and Hold, the closest packet sampling-based competitor to FS. We describe a packet sampling-based implementation of DS and analyze its key computational costs to show that router implementation is feasible. Our approach offers insights into numerous issues, including the notion of “flow quality” for understanding the relative performance of methods, and how and when employing sequence numbers is beneficial. Our work is theoretical with some simulation support and case studies on Internet data. [ABSTRACT FROM AUTHOR]

The fundamental principle underlying compressed sensing is that a signal, which is sparse under some basis representation, can be recovered from a small number of linear measurements. However, prior knowledge of the sparsity basis is essential for the recovery process. This work introduces the concept of blind compressed sensing, which avoids the need to know the sparsity basis in both the sampling and the recovery process. We suggest three possible constraints on the sparsity basis that can be added to the problem in order to guarantee a unique solution. For each constraint, we prove conditions for uniqueness, and suggest a simple method to retrieve the solution. We demonstrate through simulations that our methods can achieve results similar to those of standard compressed sensing, which rely on prior knowledge of the sparsity basis, as long as the signals are sparse enough. This offers a general sampling and reconstruction system that fits all sparse signals, regardless of the sparsity basis, under the conditions and constraints presented in this work. [ABSTRACT FROM AUTHOR]

Let X_1, \ldots, X_n be a sequence of n classical random variables and consider a sample Xs_1, \ldots, Xs_r of r \leq n positions selected at random. Then, except with (exponentially in r) small probability, the min-entropy H\min(Xs_1 \cdots Xs_r) of the sample is not smaller than, roughly, a fraction r\over n of the overall entropy H\min(X_1 \cdots X_n), which is optimal. Here, we show that this statement, originally proved in [S. Vadhan, LNCS 2729, Springer, 2003] for the purely classical case, is still true if the min-entropy H\min is measured relative to a quantum system. Because min-entropy quantifies the amount of randomness that can be extracted from a given random variable, our result can be used to prove the soundness of locally computable extractors in a context where side information might be quantum-mechanical. In particular, it implies that key agreement in the bounded-storage model—using a standard sample-and-hash protocol—is fully secure against quantum adversaries, thus solving a long-standing open problem. [ABSTRACT FROM AUTHOR]

The problem of sampling a discrete-time sequence of spatially bandlimited fields, with a bounded dynamic range, in a distributed, communication-constrained processing environment is studied. A central unit having access to the data gathered by a dense network of low-precision sensors, is required to reconstruct the field snapshots to maximum accuracy. Both deterministic and stochastic field models are considered. For stochastic fields, results are established in the almost-sure sense. The feasibility of having a flexible tradeoff between the oversampling rate (sensor density) and the analog-to-digital converter (ADC) precision, while achieving an exponential accuracy in the number of bits per Nyquist-interval per snapshot is demonstrated. This exposes an underlying “conservation of bits” principle: the bit-budget per Nyquist-interval per snapshot (the rate) can be distributed along the amplitude axis (sensor-precision) and space (sensor density) in an almost arbitrary discrete-valued manner, while retaining the same (exponential) distortion-rate characteristics. [ABSTRACT FROM AUTHOR]

Motivated by the estimation of spatio-temporal events with cheap, simple sensors, we consider the problem of estimation of a parameter θ of a signal s(x; θ) corrupted by noise assuming that only 1-bit precision dithered quantized samples are available. An estimate that does not require the knowledge of the dither signal and the noise distribution is proposed, and it is analyzed in detail under variety of nonidealities. The consistency and asymptotic normality of the estimate is established for deterministic and random sampling, imprecise knowledge of sampling locations, Gaussian and non-Gaussian noise (with possibly infinite variance), a wide class of dither distributions, and under erroneous transmission of the binary observations via binary-symmetric channels (BSC5). It is also shown that if approximation to the log-likelihood equation in the full precision case yields a good estimate, then there is a corresponding good estimate based on 1-bit dithered samples. The proposed estimate requires no more computation than the maximum-likelihood estimate for the full precision case and suffers only a logarithmic rate loss compared to the full precision case when uniform dithering is used. It is shown that uniform dithering leads to the best rate among a broad class of dither distributions. A condition under which no dithering leads to a better estimate is also given. [ABSTRACT FROM AUTHOR]