Search

We show that the classical Prony's method for recovery of a sparse signal from its consecutive Fourier coefficients can be viewed as a spectral identification problem for an unknown restriction of a known linear operator. This presents a unified point of view on various existing and novel generalizations and applications of the method, some of which are discussed in this paper.

We consider tilings $(\mathcal{Q},\Phi)$ of $\mathbb{R}^d$ where $\mathcal{Q}$ is the $d$-dimensional unit cube and the set of translations $\Phi$ is constrained to lie in a pre-determined lattice $A \mathbb{Z}^d$ in $\mathbb{R}^d$. We provide a full characterization of matrices $A$ for which such cube tilings exist when $\Phi$ is a sublattice of $A\mathbb{Z}^d$ with any $d \in \mathbb{N}$ or a generic subset of $A\mathbb{Z}^d$ with $d\leq 7$. As a direct consequence of our results, we obtain a criterion for the existence of linearly constrained frequency sets, that is, $\Phi \subseteq A\mathbb{Z}^d$, such that the respective set of complex exponential functions $\mathcal{E} (\Phi)$ is an orthogonal Fourier basis for the space of square integrable functions supported on a parallelepiped $B\mathcal{Q}$, where $A, B \in \mathbb{R}^{d \times d}$ are nonsingular matrices given a priori. Similarly constructed Riesz bases are considered in a companion paper.

The existence of a Fourier basis with frequencies in $\mathbb{R}^d$ for the space of square integrable functions supported on a given parallelepiped in $\mathbb{R}^d$, has been well understood since the 1950s. In a companion paper, we derived necessary and sufficient conditions for a parallelepiped in $\mathbb{R}^d$ to permit an orthogonal basis of exponentials with frequencies constrained to be a subset of a prescribed lattice in $\mathbb{R}^d$, a restriction relevant in many applications. In this paper, we investigate analogous conditions for parallelepipeds that permit a Riesz basis of exponentials with the same constraints on the frequencies. We provide a sufficient condition on the parallelepiped for the Riesz basis case which directly extends one of the necessary and sufficient conditions obtained in the orthogonal basis case. We also provide a sufficient condition which constrains the spectral norm of the matrix generating the parallelepiped, instead of constraining the structure of the matrix.

The complex exponentials with integer frequencies form a basis for the space of square integrable functions on the unit interval. We analyze whether the basis property is maintained if the support of the complex exponentials is restricted to possibly overlapping subsets of the unit interval. We show, for example, that if $S_1, \ldots, S_K \subset [0,1]$ are finite unions of intervals with rational endpoints that cover the unit interval, then there exists a partition of $\mathbb{Z}$ into sets $\Lambda_1, \ldots, \Lambda_K$ such that $\bigcup_{k=1}^K \{ e^{2\pi i \lambda (\cdot)} \chi_{S_k} : \lambda \in \Lambda_k \}$ is a Riesz basis for $L^2[0,1]$. Here, $\chi_S$ denotes the characteristic function of $S$., Comment: 19 pages

We study extra time-frequency shift invariance properties of Gabor spaces. For a Gabor space generated by an integer lattice, we state and prove several characterizations for its time-frequency shift invariance with respect to a finer integer lattice. The extreme cases of full translation invariance, full modulation invariance, and full time-frequency shift invariance are also considered. The results show a close analogy with the extra translation invariance of shift-invariant spaces.

In this work we characterize all ambiguities of the linear (aperiodic) one-dimensional convolution on two fixed finite-dimensional complex vector spaces. It will be shown that the convolution ambiguities can be mapped one-to-one to factorization ambiguities in the $z-$domain, which are generated by swapping the zeros of the input signals. We use this polynomial description to show a deterministic version of a recently introduced masked Fourier phase retrieval design. In the noise-free case a (convex) semi-definite program can be used to recover exactly the input signals if they share no common factors (zeros). Then, we reformulate the problem as deterministic blind deconvolution with prior knowledge of the autocorrelations. Numerically simulations show that our approach is also robust against additive noise., Comment: 17 pages, 4 figures, 50th Asilomar

We address the problem of signal reconstruction from intensity measurements with respect to a measurement frame. This non-convex inverse problem is known as phase retrieval. The case considered in this paper concerns phaseless measurements taken with respect to a Gabor frame. It arises naturally in many practical applications, such as diffraction imaging and speech recognition. We present a reconstruction algorithm that uses a nearly optimal number of phaseless time-frequency structured measurements and discuss its robustness in the case when the measurements are corrupted by noise. We show how geometric properties of the measurement frame are related to the robustness of the phaseless reconstruction. The presented algorithm is based on the idea of polarization as proposed by Alexeev, Bandeira, Fickus, and Mixon., Comment: 27 pager, 6 figures

The need of reconstructing discrete-valued sparse signals from few measurements, that is solving an undetermined system of linear equations, appears frequently in science and engineering. Whereas classical compressed sensing algorithms do not incorporate the additional knowledge of the discrete nature of the signal, classical lattice decoding approaches such as the sphere decoder do not utilize sparsity constraints. In this work, we present an approach that incorporates a discrete values prior into basis pursuit. In particular, we address unipolar binary and bipolar ternary sparse signals, i.e., sparse signals with entries in $\{0,1\}$, respectively in $\{-1,0,1\}$. We will show that phase transition takes place earlier than when using the classical basis pursuit approach and that, independently of the sparsity of the signal, at most $N/2$, respectively $3N/4$, measurements are necessary to recover a unipolar binary, and a bipolar ternary signal uniquely, where $N$ is the dimension of the ambient space. We will further discuss robustness of the algorithm and generalizations to signals with entries in larger alphabets.

We develop sampling methodology aimed at determining stochastic operators that satisfy a support size restriction on the autocorrelation of the operators stochastic spreading function. The data that we use to reconstruct the operator (or, in some cases only the autocorrelation of the spreading function) is based on the response of the unknown operator to a known, deterministic test signal.

Based on the here developed functional analytic machinery we extend the theory of operator sampling and identification to apply to operators with stochastic spreading functions. We prove that identification with a delta train signal is possible for a large class of stochastic operators that have the property that the autocorrelation of the spreading function is supported on a set of 4D volume less than one and this support set does not have a defective structure. In fact, unlike in the case of deterministic operator identification, the geometry of the support set has a significant impact on the identifiability of the considered operator class. Also, we prove that, analogous to the deterministic case, the restriction of the 4D volume of a support set to be less or equal to one is necessary for identifiability of a stochastic operator class.

We consider the problem of recovering a matrix from its action on a known vector in the setting where the matrix can be represented efficiently in a known matrix dictionary. Connections with sparse signal recovery allows for the use of efficient reconstruction techniques such as Basis Pursuit. Of particular interest is the dictionary of time-frequency shift matrices and its role for channel estimation and identification in communications engineering. We present recovery results for Basis Pursuit with the time-frequency shift dictionary and various dictionaries of random matrices.

We establish a necessary density criterion for the identifiability of time-frequency structured classes of Hilbert-Schmidt operators. The density condition is based on the density criterion for Gabor frames and Riesz bases in the space of square integrable functions. We complement our findings with examples of identifiable operator classes.

We introduce new classes of modulation spaces over phase space. By means of the Kohn-Nirenberg correspondence, these spaces induce norms on pseudo-differential operators that bound their operator norms on $L^p$-spaces, Sobolev spaces, and modulation spaces.

We study the recovery of operators with bandlimited Kohn-Nirenberg symbol from the action of such operators on a weighted impulse train, a procedure we refer to as operator sampling. Kailath, and later Kozek and the authors have shown that operator sampling is possible if the symbol of the operator is bandlimited to a set with area less than one. In this paper we develop explicit reconstruction formulas for operator sampling that generalize reconstruction formulas for bandlimited functions. We give necessary and sufficient conditions on the sampling rate that depend on size and geometry of the bandlimiting set. Moreover, we show that under mild geometric conditions, classes of operators bandlimited to an unknown set of area less than one-half permit sampling and reconstruction. A similar result considering unknown sets of area less than one was independently achieved by Heckel and Boelcskei. 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., Comment: Submitted to IEEE Transactions on Information Theory

This paper reviews some results on the identifiability of classes of operators whose Kohn-Nirenberg symbols are band-limited (called band-limited operators), which we refer to as sampling of operators. We trace the motivation and history of the subject back to the original work of the third-named author in the late 1950s and early 1960s, and to the innovations in spread-spectrum communications that preceded that work. We give a brief overview of the NOMAC (Noise Modulation and Correlation) and Rake receivers, which were early implementations of spread-spectrum multi-path wireless communication systems. We examine in detail the original proof of the third-named author characterizing identifiability of channels in terms of the maximum time and Doppler spread of the channel, and do the same for the subsequent generalization of that work by Bello. The mathematical limitations inherent in the proofs of Bello and the third author are removed by using mathematical tools unavailable at the time. We survey more recent advances in sampling of operators and discuss the implications of the use of periodically-weighted delta-trains as identifiers for operator classes that satisfy Bello's criterion for identifiability, leading to new insights into the theory of finite-dimensional Gabor systems. We present novel results on operator sampling in higher dimensions, and review implications and generalizations of the results to stochastic operators, MIMO systems, and operators with unknown spreading domains.

Boundedness results for multilinear pseudodifferential operators on products of modulation spaces are derived based on ordered integrability conditions on the short-time Fourier transform of the operators' symbols. The flexibility and strength of the introduced methods is demonstrated by their application to the bilinear and trilinear Hilbert transform., Comment: 29 pages, journal submission

We consider smoothness properties of the generator of a principal Gabor space on the real line which is invariant under some additional translation-modulation pair. We prove that if a Gabor system on a lattice with rational density is a Riesz basis for its closed linear span, and if the closed linear span, a Gabor space, has any additional translation-modulation invariance, then its generator cannot decay well in time and in frequency simultaneously., Comment: 16 pages, 1 figure

We give a stability result for sparse convolutions on $\ell^2(G)\times \ell^1(G)$ for torsion-free discrete Abelian groups $G$ such as $\mathbb{Z}$. It turns out, that the torsion-free property prevents full cancellation in the convolution of sparse sequences and hence allows to establish stability in each entry, that is, for any fixed entry of the convolution the resulting linear map is injective with an universal lower norm bound, which only depends on the support cardinalities of the sequences. This can be seen as a reverse statement of the famous Young inequality for sparse convolutions. Our result hinges on a compression argument in additive set theory., Comment: submitted to Applied and Computational Harmonic Analysis

In many radar scenarios, the radar target or the medium is assumed to possess randomly varying parts. The properties of a target are described by a random process known as the spreading function. Its second order statistics under the WSSUS assumption are given by the scattering function. Recent developments in operator sampling theory suggest novel channel sounding procedures that allow for the determination of the spreading function given complete statistical knowledge of the operator echo from a single sounding by a weighted pulse train. We construct and analyze a novel estimator for the scattering function based on these findings. Our results apply whenever the scattering function is supported on a compact subset of the time-frequency plane. We do not make any restrictions either on the geometry of this support set, or on its area. Our estimator can be seen as a generalization of an averaged periodogram estimator for the case of a non-rectangular geometry of the support set of the scattering function.

We establish the restricted isometry property for finite dimensional Gabor systems, that is, for families of time--frequency shifts of a randomly chosen window function. We show that the $s$-th order restricted isometry constant of the associated $n \times n^2$ Gabor synthesis matrix is small provided $s \leq c \, n^{2/3} / \log^2 n$. This improves on previous estimates that exhibit quadratic scaling of $n$ in $s$. Our proof develops bounds for a corresponding chaos process., Comment: 25 pages

The geometry of fundamental domains of lattices was used by Han and Wang to construct multivariate Gabor frames for separable lattices. We build upon their results to obtain Gabor frames with smooth and compactly supported window functions. For this purpose we study pairs of lattices which have equal density and allow for a common compact and star-shaped fundamental domain. The results are then extended to a larger class of lattices via symplectic equivalence.

Sampling and reconstruction of functions is a central tool in science. A key result is given by the sampling theorem for bandlimited functions attributed to Whittaker, Shannon, Nyquist, and Kotelnikov. We develop an analogous sampling theory for operators which we call bandlimited if their Kohn-Nirenberg symbols are bandlimited. We prove sampling theorems for such operators and show that they are extensions of the classical sampling theorem.

The 1987 Bourgain-Tzafriri Restricted Invertibility Theorem is one of the most celebrated theorems in analysis. At the time of their work, the authors raised the question of a possible infinite dimensional version of the theorem. In this paper, we will give a quite general definition of restricted invertibility for operators on infinite dimensional Hilbert spaces based on the notion of "density" from frame theory. We then prove that localized Bessel systems have large subsets which are Riesz basic sequences. As a consequence, we prove the strongest possible form of the infinite dimensional restricted invertibility theorem for $\ell_1$-localized operators and for Gabor frames with generating function in the Feichtinger Algebra. For our calculations, we introduce a new notion of "density" which has serious advantages over the standard form because it is independent of index maps - and hence has much broader application. We then show that in the setting of the restricted invertibility theorem, this new density becomes equivalent to the standard density., Comment: 24 pages

The classical sampling theorem for bandlimited functions has recently been generalized to apply to so-called bandlimited operators, that is, to operators with band-limited Kohn-Nirenberg symbols. Here, we discuss operator sampling versions of two of the most central extensions to the classical sampling theorem. In irregular operator sampling, the sampling set is not periodic with uniform distance. In multi-channel operator sampling, we obtain complete information on an operator by multiple operator sampling outputs.

We consider signals and operators in finite dimension which have sparse time-frequency representations. As main result we show that an $S$-sparse Gabor representation in $\mathbb{C}^n$ with respect to a random unimodular window can be recovered by Basis Pursuit with high probability provided that $S\leq Cn/\log(n)$. Our results are applicable to the channel estimation problem in wireless communications and they establish the usefulness of a class of measurement matrices for compressive sensing.

We derive a criterion on the measurability / identifiability of Multiple--Input Multiple--Output (MIMO) channels based on the size of the so-called spreading support of its subchannels. Novel MIMO transmission techniques provide high-capacity communication channels in time-varying environments and exact knowledge of the transmission channel operator is of key importance when trying to transmit information at a rate close to channel capacity.

Finite dimensional matrices having more columns than rows have no left inverses while those having more rows than columns have no right inverses. We give generalizations of these simple facts to bi--infinite matrices and use those to obtain density results for $p$--frames of time--frequency molecules in modulation spaces and identifiability results for operators with bandlimited Kohn--Nirenberg symbols.

Classical and recent results on uncertainty principles for functions on finite Abelian groups relate the cardinality of the support of a function to the cardinality of the support of its Fourier transforms. We use these results and their proofs to obtain similar results relating the support sizes of functions and their short--time Fourier transforms. Further, we discuss applications of our results. For example, we use our results to construct a class of equal norm tight Gabor frames that are maximally robust to erasures and we discuss consequences of our findings to the theory of recovering and storing signals which have sparse time--frequency representations., Comment: 31 pages, 9 figures