Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Sublinear Algorithm for Sparse Reconstruction with l2/l2 Recovery Guarantees
177
0
0.0
(
0
)
Added by
Sina Jafarpour
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Compressed Sensing aims to capture attributes of a sparse signal using very few measurements. Cand`{e}s and Tao showed that sparse reconstruction is possible if the sensing matrix acts as a near isometry on all $boldsymbol{k}$-sparse signals. This property holds with overwhelming probability if the entries of the matrix are generated by an iid Gaussian or Bernoulli process. There has been significant recent interest in an alternative signal processing framework; exploiting deterministic sensing matrices that with overwhelming probability act as a near isometry on $boldsymbol{k}$-sparse vectors with uniformly random support, a geometric condition that is called the Statistical Restricted Isometry Property or StRIP. This paper considers a family of deterministic sensing matrices satisfying the StRIP that are based on srm codes (binary chirps) and a $boldsymbol{k}$-sparse reconstruction algorithm with sublinear complexity. In the presence of stochastic noise in the data domain, this paper derives bounds on the $boldsymbol{ell_2}$ accuracy of approximation in terms of the $boldsymbol{ell_2}$ norm of the measurement noise and the accuracy of the best $boldsymbol{k}$-sparse approximation, also measured in the $boldsymbol{ell_2}$ norm. This type of $boldsymbol{ell_2 /ell_2}$ bound is tighter than the standard $boldsymbol{ell_2 /ell_1}$ or $boldsymbol{ell_1/ ell_1}$ bounds.
rate research
Read More
The sparsity in levels model recently inspired a new generation of effective acquisition and reconstruction modalities for compressive imaging. Moreover, it naturally arises in various areas of signal processing such as parallel acquisition, radar, and the sparse corruptions problem. Reconstruction strategies for sparse in levels signals usually rely on a suitable convex optimization program. Notably, although iterative and greedy algorithms can outperform convex optimization in terms of computational efficiency and have been studied extensively in the case of standard sparsity, little is known about their generalizations to the sparse in levels setting. In this paper, we bridge this gap by showing new stable and robust uniform recovery guarantees for sparse in level variants of the iterative hard thresholding and the CoSaMP algorithms. Our theoretical analysis generalizes recovery guarantees currently available in the case of standard sparsity and favorably compare to sparse in levels guarantees for weighted $ell^1$ minimization. In addition, we also propose and numerically test an extension of the orthogonal matching pursuit algorithm for sparse in levels signals.
The combination of space-time coding (STC) and continuous phase modulation (CPM) is an attractive field of research because both STC and CPM bring many advantages for wireless communications. Zhang and Fitz [1] were the first to apply this idea by constructing a trellis based scheme. But for these codes the decoding effort grows exponentially with the number of transmitting antennas. This was circumvented by orthogonal codes introduced by Wang and Xia [2]. Unfortunately, based on Alamouti code [3], this design is restricted to two antennas. However, by relaxing the orthogonality condition, we prove here that it is possible to design L2-orthogonal space-time codes which achieve full rate and full diversity with low decoding effort. In part one, we generalize the two-antenna code proposed by Wang and Xia [2] from pointwise to L2-orthogonality and in part two we present the first L2-orthogonal code for CPM with three antennas. In this report, we detail these results and focus on the properties of these codes. Of special interest is the optimization of the bit error rate which depends on the initial phase of the system. Our simulation results illustrate the systemic behavior of these conditions.
Pairwise comparison matrices have received substantial attention in a variety of applications, especially in rank aggregation, the task of flattening items into a one-dimensional (and thus transitive) ranking. However, non-transitive preference cycles can arise in practice due to the fact that making a decision often requires a complex evaluation of multiple factors. In some applications, it may be important to identify and preserve information about the inherent non-transitivity, either in the pairwise comparison data itself or in the latent feature space. In this work, we develop structured models for non-transitive pairwise comparison matrices that can be exploited to recover such matrices from incomplete noisy data and thus allow the detection of non-transitivity. Considering that individuals tastes and items latent features may change over time, we formulate time-varying pairwise comparison matrix recovery as a dynamic skew-symmetric matrix recovery problem by modeling changes in the low-rank factors of the pairwise comparison matrix. We provide theoretical guarantees for the recovery and numerically test the proposed theory with both synthetic and real-world data.
We address the exact recovery of a k-sparse vector in the noiseless setting when some partial information on the support is available. This partial information takes the form of either a subset of the true support or an approximate subset including wrong atoms as well. We derive a new sufficient and worst-case necessary (in some sense) condition for the success of some procedures based on lp-relaxation, Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS). Our result is based on the coherence mu of the dictionary and relaxes the well-known condition mu<1/(2k-1) ensuring the recovery of any k-sparse vector in the non-informed setup. It reads mu<1/(2k-g+b-1) when the informed support is composed of g good atoms and b wrong atoms. We emphasize that our condition is complementary to some restricted-isometry based conditions by showing that none of them implies the other. Because this mutual coherence condition is common to all procedures, we carry out a finer analysis based on the Null Space Property (NSP) and the Exact Recovery Condition (ERC). Connections are established regarding the characterization of lp-relaxation procedures and OMP in the informed setup. First, we emphasize that the truncated NSP enjoys an ordering property when p is decreased. Second, the partial ERC for OMP (ERC-OMP) implies in turn the truncated NSP for the informed l1 problem, and the truncated NSP for p<1.
The problem of estimating a sparse signal from low dimensional noisy observations arises in many applications, including super resolution, signal deconvolution, and radar imaging. In this paper, we consider a sparse signal model with non-stationary modulations, in which each dictionary atom contributing to the observations undergoes an unknown, distinct modulation. By applying the lifting technique, under the assumption that the modulating signals live in a common subspace, we recast this sparse recovery and non-stationary blind demodulation problem as the recovery of a column-wise sparse matrix from structured linear observations, and propose to solve it via block $ell_{1}$-norm regularized quadratic minimization. Due to observation noise, the sparse signal and modulation process cannot be recovered exactly. Instead, we aim to recover the sparse support of the ground truth signal and bound the recovery errors of the signals non-zero components and the modulation process. In particular, we derive sufficient conditions on the sample complexity and regularization parameter for exact support recovery and bound the recovery error on the support. Numerical simulations verify and support our theoretical findings, and we demonstrate the effectiveness of our model in the application of single molecule imaging.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
