Let a measurement consist of a linear combination of damped complex exponential modes, plus noise. The problem is to estimate the parameters of these modes, as in line spectrum estimation, vibration analysis, speech processing, system identification,
and direction of arrival estimation. Our results differ from standard results of modal analysis to the extent that we consider sparse and co-prime samplings in space, or equivalently sparse and co-prime samplings in time. Our main result is a characterization of the orthogonal subspace. This is the subspace that is orthogonal to the signal subspace spanned by the columns of the generalized Vandermonde matrix of modes in sparse or co-prime arrays. This characterization is derived in a form that allows us to adapt modern methods of linear prediction and approximate least squares, such as iterative quadratic maximum likelihood (IQML), for estimating mode parameters. Several numerical examples are presented to demonstrate the validity of the proposed modal estimation methods, and to compare the fidelity of modal estimation with sparse and co-prime arrays, versus SNR. Our calculations of Cram{e}r-Rao bounds allow us to analyze the loss in performance sustained by sparse and co-prime arrays that are compressions of uniform linear arrays.
In this paper, we analyze the impact of compressed sensing with complex random matrices on Fisher information and the Cram{e}r-Rao Bound (CRB) for estimating unknown parameters in the mean value function of a complex multivariate normal distribution.
We consider the class of random compression matrices whose distribution is right-orthogonally invariant. The compression matrix whose elements are i.i.d. standard normal random variables is one such matrix. We show that for all such compression matrices, the Fisher information matrix has a complex matrix beta distribution. We also derive the distribution of CRB. These distributions can be used to quantify the loss in CRB as a function of the Fisher information of the non-compressed data. In our numerical examples, we consider a direction of arrival estimation problem and discuss the use of these distributions as guidelines for choosing compression ratios based on the resulting loss in CRB.
In this paper, we will develop a systematic approach to deriving guaranteed bounds for approximate dynamic programming (ADP) schemes in optimal control problems. Our approach is inspired by our recent results on bounding the performance of greedy str
ategies in optimization of string-submodular functions over a finite horizon. The approach is to derive a string-submodular optimization problem, for which the optimal strategy is the optimal control solution and the greedy strategy is the ADP solution. Using this approach, we show that any ADP solution achieves a performance that is at least a factor of $beta$ of the performance of the optimal control solution, which satisfies Bellmans optimality principle. The factor $beta$ depends on the specific ADP scheme, as we will explicitly characterize. To illustrate the applicability of our bounding technique, we present examples of ADP schemes, including the popular rollout method.
We consider the problem of testing for the presence (or detection) of an unknown sparse signal in additive white noise. Given a fixed measurement budget, much smaller than the dimension of the signal, we consider the general problem of designing comp
ressive measurements to maximize the measurement signal-to-noise ratio (SNR), as increasing SNR improves the detection performance in a large class of detectors. We use a lexicographic optimization approach, where the optimal measurement design for sparsity level $k$ is sought only among the set of measurement matrices that satisfy the optimality conditions for sparsity level k-1. We consider optimizing two different SNR criteria, namely a worst-case SNR measure, over all possible realizations of a k-sparse signal, and an average SNR measure with respect to a uniform distribution on the locations of the up to k nonzero entries in the signal. We establish connections between these two criteria and certain classes of tight frames. We constrain our measurement matrices to the class of tight frames to avoid coloring the noise covariance matrix. For the worst-case problem, we show that the optimal measurement matrix is a Grassmannian line packing for most---and a uniform tight frame for all---sparse signals. For the average SNR problem, we prove that the optimal measurement matrix is a uniform tight frame with minimum sum-coherence for most---and a tight frame for all---sparse signals.
We study the detection error probability associated with balanced binary relay trees, in which sensor nodes fail with some probability. We consider N identical and independent crummy sensors, represented by leaf nodes of the tree. The root of the tre
e represents the fusion center, which makes the final decision between two hypotheses. Every other node is a relay node, which fuses at most two binary messages into one binary message and forwards the new message to its parent node. We derive tight upper and lower bounds for the total error probability at the fusion center as functions of N and characterize how fast the total error probability converges to 0 with respect to N. We show that the convergence of the total error probability is sub-linear, with the same decay exponent as that in a balanced binary relay tree without sensor failures. We also show that the total error probability converges to 0, even if the individual sensors have total error probabilities that converge to 1/2 and the failure probabilities that converge to 1, provided that the convergence rates are sufficiently slow.
We study the detection error probability associated with a balanced binary relay tree, where the leaves of the tree correspond to $N$ identical and independent detectors. The root of the tree represents a fusion center that makes the overall detectio
n decision. Each of the other nodes in the tree are relay nodes that combine two binary messages to form a single output binary message. In this way, the information from the detectors is aggregated into the fusion center via the intermediate relay nodes. In this context, we describe the evolution of Type I and Type II error probabilities of the binary data as it propagates from the leaves towards the root. Tight upper and lower bounds for the total error probability at the fusion center as functions of $N$ are derived. These characterize how fast the total error probability converges to 0 with respect to $N$, even if the individual sensors have error probabilities that converge to 1/2.
Fusion frame theory is an emerging mathematical theory that provides a natural framework for performing hierarchical data processing. A fusion frame is a frame-like collection of subspaces in a Hilbert space, thereby generalizing the concept of a fra
me for signal representation. In this paper, we study the existence and construction of fusion frames. We first present a complete characterization of a special class of fusion frames, called Parseval fusion frames. The value of Parseval fusion frames is that the inverse fusion frame operator is equal to the identity and therefore signal reconstruction can be performed with minimal complexity. We then introduce two general methods -- the spatial complement and the Naimark complement -- for constructing a new fusion frame from a given fusion frame. We then establish existence conditions for fusion frames with desired properties. In particular, we address the following question: Given $M, N, m in NN$ and ${lambda_j}_{j=1}^M$, does there exist a fusion frame in $RR^M$ with $N$ subspaces of dimension $m$ for which ${lambda_j}_{j=1}^M$ are the eigenvalues of the associated fusion frame operator? We address this problem by providing an algorithm which computes such a fusion frame for almost any collection of parameters $M, N, m in NN$ and ${lambda_j}_{j=1}^M$. Moreover, we show how this procedure can be applied, if subspaces are to be added to a given fusion frame to force it to become Parseval.
We consider estimating a random vector from its noisy projections onto low dimensional subspaces constituting a fusion frame. A fusion frame is a collection of subspaces, for which the sum of the projection operators onto the subspaces is bounded bel
ow and above by constant multiples of the identity operator. We first determine the minimum mean-squared error (MSE) in linearly estimating the random vector of interest from its fusion frame projections, in the presence of white noise. We show that MSE assumes its minimum value when the fusion frame is tight. We then analyze the robustness of the constructed linear minimum MSE (LMMSE) estimator to erasures of the fusion frame subspaces. We prove that tight fusion frames consisting of equi-dimensional subspaces have maximum robustness (in the MSE sense) with respect to erasures of one subspace, and that the optimal subspace dimension depends on signal-to-noise ratio (SNR). We also prove that tight fusion frames consisting of equi-dimensional subspaces with equal pairwise chordal distances are most robust with respect to two and more subspace erasures. We call such fusion frames equi-distance tight fusion frames, and prove that the chordal distance between subspaces in such fusion frames meets the so-called simplex bound, and thereby establish connections between equi-distance tight fusion frames and optimal Grassmannian packings. Finally, we present several examples for construction of equi-distance tight fusion frames.
