Search

In estimating frequencies given that the signal waveforms are undersampled multiple times, Xia et. al. proposed to use a generalized version of Chinese remainder Theorem (CRT), where the moduli are $M_1, M_2, \cdots, M_k$ which are not necessarily pairwise coprime. If the errors of the corrupted remainders are within $\tau=\sds \max_{1\le i\le k} \min_{\stackrel{1\le j\le k}{j\neq i}} \frac{\gcd(M_i,M_j)}4$, their schemes can be used to construct an approximation of the solution to the generalized CRT with an error smaller than $\tau$. Accurately finding the quotients is a critical ingredient in their approach. In this paper, we shall start with a faithful historical account of the generalized CRT. We then present two treatments of the problem of solving generalized CRT with erroneous remainders. The first treatment follows the route of Wang and Xia to find the quotients, but with a simplified process. The second treatment considers a simplified model of generalized CRT and takes a different approach by working on the corrupted remainders directly. This approach also reveals some useful information about the remainders by inspecting extreme values of the erroneous remainders modulo $4\tau$. Both of our treatments produce efficient algorithms with essentially optimal performance. Finally, this paper constructs a counterexample to prove the sharpness of the error bound $\tau$.

Inspired by an interesting idea of Cai and Zhang, we formulate and prove the convex $k$-sparse decomposition of vectors which is invariant with respect to $\ell_1$ norm. This result fits well in discussing compressed sensing problems under RIP, but we believe it also has independent interest. As an application, a simple derivation of the RIP recovery condition $\delta_k+\theta_{k,k} < 1$ is presented., Comment: Add some comments for the noise case

The class of Fourier matrices is of special importance in compressed sensing (CS). This paper concerns deterministic construction of compressed sensing matrices from Fourier matrices. By using Katz' character sum estimation, we are able to design a deterministic procedure to select rows from a Fourier matrix to form a good compressed sensing matrix for sparse recovery. The sparsity bound in our construction is similar to that of binary CS matrices constructed by DeVore which greatly improves previous results for CS matrices from Fourier matrices. Our approach also provides more flexibilities in terms of the dimension of CS matrices. As a consequence, our construction yields an approximately mutually unbiased bases from Fourier matrices which is of particular interest to quantum information theory. This paper also contains a useful improvement to Katz' character sum estimation for quadratic extensions, with an elementary and transparent proof. Some numerical examples are included., Comment: 17 pages

In many compressed sensing applications, linear programming (LP) has been used to reconstruct a sparse signal. When observation is noisy, the LP formulation is extended to allow an inequality constraint and the solution is dependent on a parameter $\delta$, related to the observation noise level. Recently, some researchers also considered quadratic programming (QP) for compressed sensing signal reconstruction and the solution in this case is dependent on a Lagrange multiplier $\beta$. In this work, we investigated the relation between $\delta$ and $\beta$ and derived an upper and a lower bound on $\beta$ in terms of $\delta$. For a given $\delta$, these bounds can be used to approximate $\beta$. Since $\delta$ is a physically related quantity and easy to determine for an application while there is no easy way in general to determine $\beta$, our results can be used to set $\beta$ when the QP is used for compressed sensing. Our results and experimental verification also provide some insight into the solutions generated by compressed sensing.

In this paper we show that if the restricted isometry constant $\delta_k$ of the compressed sensing matrix satisfies \[ \delta_k < 0.307, \] then $k$-sparse signals are guaranteed to be recovered exactly via $\ell_1$ minimization when no noise is present and $k$-sparse signals can be estimated stably in the noisy case. It is also shown that the bound cannot be substantively improved. An explicitly example is constructed in which $\delta_{k}=\frac{k-1}{2k-1} < 0.5$, but it is impossible to recover certain $k$-sparse signals.