Search

In this work, we show that the incoherence alone is sufficient to establish the statistical restricted isometry property (StRIP) and statistical incoherence property (SInCoP) for unit norm tight frames (UNTFs). Further, we derive three simple properties that binary matrices need to satisfy, in order to produce incoherent UNTFs (IUNTFs) with high redundancy (ratio of the number of columns to the number of rows) via an existing embedding operation. We show that biadjacency matrices corresponding to biregular graphs satisfy the required properties. Thereby, we provide a connection between graph theory and the construction of IUNTFs. We also provide a bouquet of constructions of IUNTFs from finite fields and combinatorial designs. Another important aspect of our construction is that the sparse recovery guarantees for the embedded IUNTFs can in fact be translated to the constituent binary matrix. We show that if the constituent $m\times M$ binary matrix has constant row and column weight, it can support sparse recovery through $\ell_{1}$ -minimization for all but an $\epsilon$ -fraction of $t$ -sparse signals chosen from a random signal model, provided $m=O(t(\log(\frac{M}{\epsilon}))^{3}),$ which is a significant improvement over the existing $m=O(t^{2})$ bound, where $m$ denotes the number of measurements. Also, the StRIP and SInCoP based approach results in matrices whose column size is exponential in the fourth root of the row size. To the best of our knowledge, this is the first construction of deterministic matrices satisfying StRIP and SInCoP with such high redundancy.

Direction-of-arrival (DOA) estimation finds applications in many areas of science and engineering. In these applications, sparse arrays such as minimum redundancy arrays, nested arrays, and coprime arrays can be exploited to resolve $O(N^2)$ uncorrelated sources using $N$ physical sensors. Recently, it has been shown that correlation subspaces , which reveal the structure of the covariance matrix, help to improve some existing DOA estimators. However, the bases, the dimension, and other theoretical properties of correlation subspaces remain to be investigated. This paper proposes generalized correlation subspaces in one and multiple dimensions. This leads to new insights into correlation subspaces and DOA estimation with prior knowledge. First, it is shown that the bases and the dimension of correlation subspaces are fundamentally related to difference coarrays , which were previously found to be important in the study of sparse arrays. Furthermore, generalized correlation subspaces can handle certain forms of prior knowledge about source directions. These results allow one to derive a broad class of DOA estimators with improved performance. It is demonstrated through examples that using sparse arrays and generalized correlation subspaces, DOA estimators with source priors exhibit better estimation performance than those without priors, in extreme cases like low SNR and limited snapshots.

Linear [one-dimensional (1-D)] sparse arrays such as nested arrays and minimum redundancy arrays have hole-free difference coarrays with $O(N^2)$ virtual sensor elements, where $N$ is the number of physical sensors. The hole-free property makes it easier to perform beamforming and DOA estimation in the coarray domain which behaves like an uniform linear array. The $O(N^2)$ property implies that $O(N^2)$ uncorrelated sources can be identified. For the 2-D case, planar sparse arrays with hole-free coarrays having $O(N^2)$ elements have also been known for a long time. These include billboard arrays, open box arrays (OBA), and 2-D nested arrays. Their merits are similar to those of the 1-D sparse arrays mentioned above, although identifiability claims regarding $O(N^2)$ sources have to be handled with more care in 2-D. This paper introduces new planar sparse arrays with hole-free coarrays having $O(N^2)$ elements just like the OBA, with the additional property that the number of sensor pairs with small spacings such as $\lambda /2$ decreases, reducing the effect of mutual coupling. The new arrays include half-open box arrays, half-open box arrays with two layers, and hourglass arrays. Among these, simulations show that hourglass arrays have the best estimation performance in presence of mutual coupling.

In array processing, mutual coupling between sensors has an adverse effect on the estimation of parameters (e.g., DOA). Sparse arrays such as nested arrays, coprime arrays, and minimum redundancy arrays (MRA) have reduced mutual coupling compared to uniform linear arrays (ULAs). These arrays also have a difference coarray with $O\left({N}^{2}\right)$ virtual elements, where $N$ is the number of physical sensors, and can therefore resolve $O\left({N}^{2}\right)$ uncorrelated source directions. But these well-known sparse arrays have disadvantages: MRAs do not have simple closed-form expressions for the array geometry; coprime arrays have holes in the coarray; and nested arrays contain a dense ULA in the physical array, resulting in significantly higher mutual coupling than coprime arrays and MRAs. In a companion paper, a sparse array configuration called the (second-order) super nested array was introduced, which has many of the advantages of these sparse arrays, while removing most of the disadvantages. Namely, the sensor locations are readily computed for any $N$ (unlike MRAs), and the difference coarray is exactly that of a nested array, and therefore hole-free. At the same time, the mutual coupling is reduced significantly (unlike nested arrays). In this paper, a generalization of super nested arrays is introduced, called the $Q$ th-order super nested array. This has all the properties of the second-order super nested array with the additional advantage that mutual coupling effects are further reduced for $Q > 2$ . Many theoretical properties are proved and simulations are included to demonstrate the superior performance of these arrays.

In array processing, mutual coupling between sensors has an adverse effect on the estimation of parameters (e.g., DOA). While there are methods to counteract this through appropriate modeling and calibration, they are usually computationally expensive, and sensitive to model mismatch. On the other hand, sparse arrays, such as nested arrays, coprime arrays, and minimum redundancy arrays (MRAs), have reduced mutual coupling compared to uniform linear arrays (ULAs). With $N$ denoting the number of sensors, these sparse arrays offer $O({N}^{2})$ freedoms for source estimation because their difference coarrays have $O({N}^{2})$ -long ULA segments. But these well-known sparse arrays have disadvantages: MRAs do not have simple closed-form expressions for the array geometry; coprime arrays have holes in the coarray; and nested arrays contain a dense ULA in the physical array, resulting in significantly higher mutual coupling than coprime arrays and MRAs. This paper introduces a new array called the super nested array, which has all the good properties of the nested array, and at the same time achieves reduced mutual coupling. There is a systematic procedure to determine sensor locations. For fixed $N$ , the super nested array has the same physical aperture, and the same hole-free coarray as does the nested array. But the number of sensor pairs with small separations ( $\lambda /2,2\times \lambda /2$ , etc.) is significantly reduced. Many theoretical properties are proved and simulations are included to demonstrate the superior performance of these arrays. In the companion paper, a further extension called the $Q$ th-order super nested array is developed, which further reduces mutual coupling.

This paper shows, under general input data models, how block memoryless equalizers should be formulated considering reduced-redundancy transmissions for superfast detection. We propose linear and DFE-based, both multicarrier (MC) and single-carrier-frequency-domain (SC-FD) transceivers, along with efficient methods for the equalizer calculation, in a unified manner. We argue that, under a one-tap block decision feedback, transmitted redundancy can be reduced below the minimum |(L-1)/2| samples allowed in the linear case, where L is the channel length, even down to zero-redundancy, with improved BER performance. This is quantified in light of the optimal reconstruction delay set for a minimum-norm zero-forcing feedforward matrix in terms of the channel zeros location. The proposed MC and SC-FD block DFEs do not cancel inter-block-interference (IBI) via zeros-jamming; Instead, it removes IBI completely, in part by decision-feedback, and in part by zero-padding, which allows for much lower redundancy transmissions. The remaining ISI is further eliminated through a one-step block-iterative-generalized-DFE (BI-GDFE) obtained in the minimum-mean-square-error (MMSE) sense. Unlike computationally demanding block DFEs that eliminate ISI via successive cancelation, the proposed DFE schemes are as efficient as a superfast block-linear equalizer, requiring at most 3 receive branches to realize the order- M feedforward matrices in O(M logM) operations.

This paper presents new linear time-invariant (LTI) block-based transceivers which employ a reduced amount of redundancy to eliminate the interblock interference. The proposals encompass both multicarrier and single-carrier systems with either zero-forcing or minimum mean-square error (MSE) equalizers. The amount of redundancy ranges from the minimum, [L/2], to the most commonly used value, L, assuming a channel-impulse response of order L. The resulting transceivers allow for superfast equalization of the received data blocks, since they only use fast Fourier transforms and single-tap equalizers in their structures. The paper also includes an MSE analysis of the proposed transceivers with respect to the amount of redundancy. Indeed, we demonstrate that larger amounts of transmitted redundant elements lead to lower MSE of symbols at the receiver end. Computer simulations indicate that, by choosing an appropriate amount of redundancy, our proposals can achieve higher throughputs than the standard superfast multicarrier and single-carrier systems, while keeping the same asymptotic computational complexity for the equalization process.

This paper analyzes both the mean-square error (MSE) and the mutual information in block-based transceivers that employ zero-padding. We consider both linear transceivers and decision-feedback equalizers (DFE) that minimize the MSE of symbols. These systems may enjoy the zero-forcing property or not, and may use unitary precoder or not. We demonstrate mathematically that the MSE/mutual information related to these transceivers are: (i) monotone increasing/decreasing functions of the number of transmitted symbols per block; (ii) monotone decreasing/increasing functions of the number of redundant data used in the equalization process of a block; and (iii) increased/decreased whenever non-minimum phase channels are utilized, instead of their minimum phase counterparts, assuming that one does not use the whole received data block to estimate the transmitted signal. As consequence of the former results, we also prove that, for both DFE and minimum error-probability systems, the average error-probability of symbols maintains the same monotonic behavior as the average MSE of symbols. The theoretical results do not include pure minimum MSE-based systems.

The Laplacian pyramid (LP) is a multiresolution representation introduced originally for images, and it has been used in many applications. A major shortcoming of the LP representation is that it is oversampled. The dependency among the LP coefficients is studied in this paper. It is shown that whenever the LP compression filter is interpolatory, the redundancy in the LP coefficients can be removed effortlessly by merely discarding some of the LP coefficients. Furthermore, it turns out that the remaining, now critically sampled, LP coefficients are actually the coefficients of a wavelet filter bank. As a result, a new algorithm for designing a nonredundant wavelet filter bank from non-biorthogonal lowpass filters is obtained. Our methodology presented in this paper does not depend on the spatial dimension of the data or the dilation matrix for sampling.

In this paper, we address the problem of redundancy reduction of high-dimensional noisy signals that may contain anomaly (rare) vectors, which we wish to preserve. Since anomaly data vectors contribute weakly to the l2-norm of the signal as compared to the noise, l2 -based criteria are unsatisfactory for obtaining a good representation of these vectors. As a remedy, a new approach, named Min-Max-SVD (MX-SVD) was recently proposed for signal-subspace estimation by attempting to minimize the maximum of data-residual l2-norms, denoted as l2,l and designed to represent well both abundant and anomaly measurements. However, the MX-SVD algorithm is greedy and only approximately minimizes the proposed l2,l-norm of the residuals. In this paper we develop an optimal algorithm for the minization of the l2,l-norm of data misrepresentation residuals, which we call Maximum Orthogonal complements Optimal Subspace Estimation (MOOSE). The optimization is performed via a natural conjugate gradient learning approach carried out on the set of n dimensional subspaces in IRm, m ≫ n, which is a Grassmann manifold. The results of applying MOOSE, MX-SVD, and l2- based approaches are demonstrated both on simulated and real hyperspectral data.

This work devises a minimum bit error rate (BER) block-based precoder used in block transmission systems with the proposed cascaded zero-forcing (ZF) equalizer. The study framework is developed as follows. For a block-based precoder, a received signal model is formulated for the two redundancy schemes, viz., trailing-zeros (TZ) and cyclic-prefix (CP). By exploiting the property of oblique projection, a cascaded equalizer for block transmission systems is proposed and implemented with a scheme, in which the inter-block interference (IBI) is completely eliminated by the oblique projection and followed by a matrix degree-of-freedom for inter-symbol interference (ISI) equalization. With the available channel state information at the transmitter side, the matrix for ISI equalization of the cascaded equalizer is utilized to design an optimum block-based precoder, such that the BER is minimized, subject to the ISI-free and the transmission power constraints. Accordingly, the cascaded equalizer with the ISI-free constraint yields a cascaded ZF equalizer. Theoretical derivations and simulation results confirm that the proposed framework not only retains identical BER performance to previous works for cases with sufficient redundancy, but also allows their results to be extended to the cases of insufficient redundancy.

In this paper, we address the problem of redundancy-reduction of high-dimensional noisy signals that may contain anomaly (rare) vectors, which we wish to preserve. For example, when applying redundancy reduction techniques to hyperspectral images, it is essential to preserve anomaly pixels for target detection purposes. Since rare-vectors contribute weakly to the -norm of the signal as compared to the noise, -based criteria are unsatisfactory for obtaining a good representation of these vectors. The proposed approach combines and norms for both signal-subspace and rank determination and considers two aspects: One aspect deals with signal-subspace estimation aiming to minimize the maximum of data-residual -norms, denoted as , for a given rank conjecture. The other determines whether the rank conjecture is valid for the obtained signal-subspace by applying Extreme Value Theory results to model the distribution of the noise -norm. These two operations are performed alternately using a suboptimal greedy algorithm, which makes the proposed approach practically plausible. The algorithm was applied on both synthetically simulated data and on a real hyperspectral image producing better results than common -based methods.

In this paper, the problem of designing finite-impulse-response (FIR) equalizers for multiple-input multiple-output (MIMO) FIR channels is considered. It is shown that an arbitrary MIMO frequency-selective channel can be rendered FIR equalizable by a suitable filter bank (FB) precoding operation that introduces redundancy at the transmitter. The expression for the minimum redundancy required to ensure FIR invertibility is derived. The analysis is extended to the case of MIMO multicarrier modulation. Optimum zero-forcing (ZF) and minimum mean-squared error (MMSE) solutions for the FIR equalizer are derived. Simulation results are provided to demonstrate that the proposed scheme achieves better performance than the block-processing methods while supporting a higher data rate.

International audience; This paper describes a new family of error-resilient variable-length source codes (VLCs). The codes introduced can be regarded as generalizations of the multiplexed codes described by Je´gou and Guillemot. They allow to exploit first-order source statistics while, at the same time, being resilient to transmission errors. The design principle consists of creating a codebook of fixed-length codewords (FLCs) for high-priority information and in using the inherent codebook redundancy to describe low-priority information. The FLC codebook is partitioned into equivalence classes according to the conditional probabilities of the high-priority source. The error propagation phenomenon, which may result from the memory of the source coder, is controlled by choosing appropriate codebook partitions and index assignment strategies. In particular, a context-dependent index assignment strategy, called crossed-index assignment, is described. For the symbol error rate criterion, the approach turns out to maximize the cardinality of a set of codewords, called the code kernel, offering synchronization properties. The decoder resynchronization capability is shown to be further increased by periodic use of memoryless multiplexed codes. Theoretical and practical performances in terms of compression efficiency and error resilience are analyzed.

Redundant bases or frames are a promising technique for multiple description signal coding. Frames can provide sufficient redundancy for recovery in case of coefficient losses due, for instance, to packet transmission errors. In this paper, we consider the problem of dual frame computation in the context of finite impulse response (FIR) analysis and synthesis filterbanks. In particular, we propose an algorithm for dual frame computation which recovers the missing frame coefficients, followed by synthesis with the original filterbank. It is shown that the algorithm operates locally and allows for reduced complexity and low-delay reconstruction of the original signal. The case of excessive losses and incomplete bases is also considered. Experiments are provided to evaluate the algorithm performance and test its applicability in practical contexts.

In this paper, we investigate the equalization and channel identification for space-time block coded signals over a frequency-selective multiple-input multiple-output (MIMO) channel. The equalization has been considered by taking into account the cyclostationarity of space-time block coded signals. The minimum mean square error (MMSE) solutions have been derived for the linear and decision feedback (DF) equalizers. The channel estimation is required for the equalization. With known symbols (as pilot symbols), MIMO channels can be estimated. In addition, due to the redundancy induced by space-time block code, it is possible to identify MIMO channels blindly using the subspace method. We consider both blind and semi-blind channel estimation for MIMO channels. It is shown that the semi-blind channel estimate has fewer estimation errors, and it results in less (bit error rate) performance degradation of the MMSE linear and DF equalizers.

This paper proposes a rate-distortion optimal a posteriori quantization scheme for Matching Pursuit coefficients. The a posteriori quantization applies to a Matching Pursuit expansion that has been generated off-line, and cannot benefit of any feedback loop to the encoder in order to compensate for the quantization noise. The redundancy of the Matching Pursuit dictionary provides an indicator of the relative importance of coefficients and atom indices, and subsequently on the quantization error. It is used to define a universal upper-bound on the decay of the coefficients, sorted in decreasing order of magnitude. A new quantization scheme is then derived, where this bound is used as an Oracle for the design of an optimal a posteriori quantizer. The latter turns the exponentially distributed coefficient entropy-constrained quantization problem into a simple uniform quantization problem. Using simulations with random dictionaries, we show that the proposed exponentially upper-bounded quantization (EUQ) clearly outperforms classical schemes. Stepping on the ideal Oracle-based approach, a sub-optimal adaptive scheme is then designed that approximates the EUQ but still outperforms competing quantization methods in terms of rate-distortion characteristics. Finally, the proposed quantization method is studied in the context of image coding. It performs similarly to state-of-the-art coding methods (and even better at low rates), while interestingly providing a progressive stream, very easy to transcode and adapt to changing rate constraints.

A multiple description transform coding (MDTC) method has been reported previously. The redundancy rate distortion (RRD) performance of this coding scheme for the independent and identically distributed (i.i.d.) two-dimensional (2-D) Gaussian source has been analyzed using mean squared error (MSE) as the distortion measure. At the small redundancy region, the MDTC scheme can achieve excellent RRD performance because a small increase in redundancy can reduce the single description distortion at a rate faster than exponential, but the performance of MDTC becomes increasingly poor at larger redundancies. This paper describes a generalization of the MDTC (GMDTC) scheme, which introduces redundancy both by transform and through correcting the error resulting from a single description. Its RRD performance is closer to the theoretical bound in the entire range of redundancy. Analysis both for a single pair of variables and for multiple variables is presented.

This paper presents a general framework for space-time codes (STCs) that encompasses a number of previously proposed STC schemes as special cases. The STCs considered are block codes that employ arbitrary redundant linear precoding of a given data sequence together with embedded training symbols, if any. The redundancy introduced by the linear precoding imposes structure on the received data that under certain conditions can be exploited for blind or semi-blind estimation of the transmitted sequence, a linear receiver that recovers the sequence, or both simultaneously. Algorithms based on this observation are developed for the single-user flat-fading case and then extended to handle multiple users, frequency-selective fading, as well as situations where the channel is rank deficient, or there are fewer receive than transmit antennas.

This paper proposes a new blind channel estimation method for orthogonal frequency division multiplexing (OFDM) systems. The algorithm makes use of the redundancy introduced by the cyclic prefix to identify the channel based on a subspace approach. Thus, the proposed method does not require any modification of the transmitter and applies to most existing OFDM systems. Semi-blind procedures taking advantage of training data are also proposed. These can be training symbols or pilot tones, the latter being used for solving the intrinsic indetermination of blind channel estimation. Identifiability results are provided, showing that in the (theoretical) situation where channel zeros are located on subcarriers, the algorithm does not ensure uniqueness of the channel estimation, unless the full noise subspace is considered. Simulations comparing the proposed method with a decision-directed channel estimator finally illustrates the performance of the proposed algorithm.

There has been great interest in the design of filterbank transceivers. Usually, with proper time domain equalization, the channel is modeled as an FIR filter. It is known that for FIR channels, the introduction of certain redundancy allows the receiver to cancel intersymbol interference (ISI) completely, and channel equalization is performed implicitly using FIR transceivers. This scheme allows us to trade bandwidth for ISI cancellation. In this paper, we derive the minimum redundancy required for the existence of FIR transceivers for a given channel. We see that the minimum redundancy is directly related to the zeros of the channel and to the Smith form of an appropriately defined channel matrix.

Joint mitigation of time- and frequency-selective fading is an important and challenging problem in mobile communications. Relying on transmitter-induced redundancy, we propose novel channel estimation and symbol recovery approaches for blind identification and equalization of time- and frequency-selective channels, where the time variation is modeled deterministically by a basis expansion. The resulting statistical algorithm enables the usage of a single antenna, dispenses with channel disparity conditions of existing approaches, and allows channel order overestimation. In addition, new deterministic algorithms for generalized OFDM systems are introduced that produce reliable estimates with few data points at high SNR's. Simulations illustrate the approaches developed.

Many blind channel equalization/identification algorithms are derived assuming the transmitted information sequence to be white. In practical communication systems, redundancy is added to the source sequence in order to detect and correct symbol errors in the receiver. It is not obvious how channel encoding will affect the assumption of whiteness. The autocorrelation function of some commonly used channel codes is analyzed in order to study the validity of assumptions used in blind equalization. The codes are presented in terms of a Markov model for which the autocorrelation is analytically expressed. The various encoded sequences are used in a prediction error based blind equalizer, and the performance is empirically compared with the case of unencoded data. A blind equalization example using a practical GSM speech encoder combined with a convolutional channel encoder is also given.

Developing fast and robust methods for identifying multiple FIR channels driven by an unknown common source is important for wireless communications, speech reverberation cancellation, and other applications. In this correspondence, we present a new method that exploits a minimum noise subspace (MNS). The MNS is computed from a set of channel output pairs that form a "tree". The "tree" exploits, with minimum redundancy, the diversity among all channels. The MNS method is much more efficient in computation than a standard subspace method. The noise robustness of the MNS method is illustrated by simulation.

It is shown that, even in the very basic direct-form symmetric FIR (finite impulse response) filter structure, redundancy exists in terms of additive complexity. Methods for removing it are presented. A conventional direct-form implementation of an L-tap symmetric FIR filter requires L/2 or (L+1)/2 multiplications, L-1 additions, and L-1 delay units. The symmetry is exploited in such a way that the number of additions is significantly reduced, while the number of multiplications and the memory requirement remain the same. It is shown that the additive complexity can be reduced nearly to L/2. A complete solution is provided, for any L, to the derivation of the filter structure that requires the minimal number of additions, L/2 or (L+1)/2 multiplications, and L-1 delay units. Thus a new class of structures and algorithms for symmetric FIR filters is obtained. >

Redundancy averaging is a spatial averaging technique that can lead to improved spatial correlation matrix estimates in terms of reduced intersignal coherence and reduced variance, but it has the undesirable characteristic of potentially biasing direction estimates. It is shown that for linear equally spaced arrays, any basis induced in the direction estimates by redundancy averaging vanishes as the number of sensors becomes large. >

The lag redundancy averaging (LRA) method for processing linear equispaced arrays is examined. LRA is a simple procedure for estimating Toeplitz covariance matrices, which can be computed efficiently by means of spatial fast Fourier transform (FFT) algorithms. The effect of LRA on the performance of the MUSIC method for uncorrelated sources is investigated. Closed-form expressions for the asymptotic bearing accuracy are obtained. It is shown, for the single source case, that the LRA method is asymptotically efficient. For two equipowered sources, it is shown that while the resolution threshold of the LRA method is superior to that of standard MUSIC, its asymptotic accuracy is inferior. >

It is well known that the performance of direction-of-arrival estimation and beamforming algorithms degrades in the presence of correlated signals. Since techniques like spatial and weighted smoothing, which were developed for decorrelating the signals, suffer from reduced effective aperture, several authors have recently proposed redundancy averaging as an alternative spatial averaging method. Considering a two-source signal model and the asymptotic case, the authors show analytically that this technique results in an eigenstructure which is inconsistent with that of the underlying signal model. In particular, the resulting signal subspace fills up the whole M-dimensional space, where M is the array size, and the resulting covariance matrix is not guaranteed to be nonnegative definite. It is shown that complete decorrelation is not possible with this method even if the array size is infinitely large. >