Recently, we proposed weight-constrained nested arrays (WCNA) that have holes in the difference coarray at lags 1 and 2. While this helps in reducing the impact of mutual coupling, the ULA segment in the coarray is ‘one-sided’ from lag L1to L2where 012. In this work, we propose to use covariance interpolation to effectively utilize such arrays having ‘central’ holes in the coarray. After interpolation, a larger Toeplitz matrix is generated, which is used to estimate directions of arrivals (DOAs) using root-MUSIC. We demonstrate that using this approach, we can accurately identify up to twice as many DOAs as what is possible using only the one-sided ULA segment in coarray. Even when the number of DOAs is small, the DOA estimation error after interpolation is over an order of magnitude smaller than that using only the one-sided ULA segment in coarray. Thus, we can mitigate the disadvantage of having central holes in the coarray while maintaining the advantage of WCNAs in reducing the impact of mutual coupling on DOA estimation. This interpolation approach can also be used for other arrays from the literature that have central holes in the coarray, such as CADiS.

Recently, several sparse array constructions have been proposed to reduce the effect of mutual coupling on the direction of arrival (DOA) estimation, by reducing the number of sensor pairs with small separations. For a large number of sensors N and under aperture constraint, $\mathcal{O}\left( {{N^2}} \right)$ degrees of freedom and $\mathcal{O}\left( {{N^2}} \right)$ aperture may not be of interest, or desirable. In this paper, we consider sparse arrays with $\mathcal{O}(N)$ aperture and enforce the coarray weights at smaller lags to be zero. This helps reduce the effect of mutual coupling while maintaining $\mathcal{O}(N)$ aperture, which is desirable when there is an aperture constraint. We describe several specific ways in which such arrays can be generated by appropriately dilating uniform linear arrays and augmenting them with a few additional sensors. We perform Monte-Carlo simulations to demonstrate that the proposed arrays perform well in the presence of strong mutual coupling, unlike the uniform linear array. They can also perform better compared to $\mathcal{O}\left( {{N^2}} \right)$ aperture sparse arrays when the array aperture is constrained.

It is known that the Minimum Variance Distortionless Response (MVDR) beamformer or Capon beamformer has all its zeros on the unit circle of the$z$-plane under some standard assumptions. A number of proofs have been given in the literature. An observation is made here which makes the proof of the result considerably simpler.1

Beamspace processing for DOA estimation offers low computational complexity and high DOA resolution. Moreover, unlike classical beamspace methods, convolutional beamspace (CBS) preserves the Vandermonde structure of uniform linear array output, so no additional preparation is needed to apply root-MUSIC. In this paper, theoretical MSE of CBS is given when MUSIC or root-MUSIC is used. Error variance can be derived from the asymptotic probability distribution of the eigenvectors of an average finite-snapshot covariance matrix. Meanwhile, the bias due to the filtered stopband sources is given by first-order perturbation analysis. Known advantages of CBS are confirmed by the MSE analysis. For example, CBS yields smaller MSE for correlated sources than element-space. The theoretical results are verified by simulations.

Coprime arrays are normally used to identify more sources than sensors, using the coarray domain. They can also be used directly in element-space and still have benefits of better accuracy and resolution compared to ULAs. An invariance is buried in each of the two sparse ULAs which constitute a coprime array. In this paper, ESPRIT is applied separately to each ULA to yield a set of residues of DOAs, and residues from the ULAs are paired to resolve DOAs. With unitary ESPRIT, residues are automatically paired in the real and imaginary parts of the eigenvalues of a matrix obtained from outputs of the two ULAs. These eigenvalues are proved to be distinct, so the eigendecomposition is unique. Previous works used traditional ESPRIT for similar application, so the eigenvalues corresponding to each invariance were complex; elaborate steps were taken to pair residues. Advantages of the proposed method are demonstrated by simulations.

Ramanujan sums have been shown to have interesting applications in signal processing. Ramanujan subspaces, Ramanujan dictionaries, and Ramanujan filter banks are useful in representing and denoising discrete-time periodic signals. In this paper, we theoretically investigate an ideal interpolation filter model for Ramanujan subspace signals wherein an expander ↑ M is followed by the ideal q-th Ramanujan filter Cq(ejω). The output space of this interpolation filter is, in general, only a proper subspace of the q-th Ramanujan subspace ${{\mathcal{S}}_q}$. For the special case when M and q are coprime, we prove that the output space is the entire Ramanujan subspace. We also discuss a more general form of this model for the representation of periodic signals, which may have a potential application in denoising periodic signals. When M and q are not coprime, we provide a bound on the dimension of the output space of the interpolation filter. For this general case, we also conjecture that the provided bound in fact equals the dimension of the output space.

Rational arrays were recently proposed for direction of arrival (DOA) estimation, and some of their advantages were discussed. In this paper we discuss further advantages of rational arrays, by considering their difference coarrays. Although integer arrays such as nested arrays, and coprime arrays are well-known for their ability to identify ${{\mathcal{O}}}\left({{m^2}}\right)$ uncorrelated sources using m sensors through difference coarray domain, they can do so only when a large enough aperture is available. However, rational arrays can do so even when the aperture is constrained. We demonstrate that adding a few sensors at non-integer locations in an otherwise integer array can add a large number of fractional lags at which autocorrelation can be estimated. Appropriately designed sparse integer arrays can also be scaled to produce rational arrays that fit available aperture and have large uniform coarray segments at rational locations. Monte-Carlo simulations are provided to demonstrate the advantages, and practical issues associated with shrinking, such as increased mutual coupling, are discussed.

The recently introduced convolutional beamspace (CBS) method has some advantages over traditional beamspace methods in array processing. This paper introduces a variant which uses IIR instead of FIR filters in the convolutional layer. In CBS, the sources falling in the stopband are assumed to be sufficiently attenuated so that we can identify the pass-band DOAs. An IIR filter often requires a much lower order for the same set of magnitude response specifications. Hence, the computational complexity of IIR-CBS can be smaller than FIR-CBS. Moreover, IIR-CBS can even give smaller DOA estimation errors than FIR-CBS because the longer FIR filter length means shorter steady-state filter output length, which leads to larger estimation errors. The advantages of IIR-CBS are verified by numerical examples.

Linear arrays used in array processing usually have sensor positions riλ/2 where λ is the wavelength of the impinging signals and riare integers. This paper considers rational arrays, where riare rational numbers. In particular, sparse rational arrays such as coprime rational arrays are introduced. In order to do this, some rational extensions of integer number theoretic concepts such as greatest common divisor and coprime numbers are required, which are introduced as well. The advantages of rational arrays are demonstrated with the help of rational coprime arrays. For example, they improve the accuracy of DOA estimation when the sensors have to be distributed with a fixed aperture constraint.

A new method to design the filter for convolutional beamspace (CBS), called Capon-CBS, is proposed. The idea is to design the filter to be a sliding Capon beamformer. Such design takes input statistics into account, so it can do a better job of suppressing the sources that fall in the stopband. Capon-CBS can offer higher probability of resolution and smaller mean square error for DOA estimation, as demonstrated in the simulations. Moreover, like traditional CBS, Capon-CBS also has the advantage of low computational complexity.

Ramanujan filter banks (RFB) have in the past been used to identify periodicities in data. These are analysis filter banks with no synthesis counterpart for perfect reconstruction of the original signal, so they have not been useful for denoising periodic signals. This paper proposes to use a hybrid analysis-synthesis framework for denoising discrete-time periodic signals. The synthesis occurs via a pruned dictionary designed based on the output energies of the RFB analysis filters. A unique property of the framework is that the denoised output signal is guaranteed to be periodic unlike any of the other methods. For a large range of input noise levels, the proposed approach achieves a stable and high SNR gain outperforming many traditional denoising techniques.

One-bit quantization has attracted attention in massive MIMO, radar, and array processing, due to its simplicity, low cost, and capability of parameter estimation. Specifically, the shape of the covariance of the unquantized data can be estimated from the arcsine law and onebit data, if the unquantized data is Gaussian. However, in practice, the Gaussian assumption is not satisfied due to outliers. It is known from the literature that outliers can be modeled by complex elliptically symmetric (CES) distributions with heavy tails. This paper shows that the arcsine law remains applicable to CES distributions. Therefore, the normalized scatter matrix of the unquantized data can be readily estimated from one-bit samples derived from CES distributions. The proposed estimator is not only computationally fast but also robust to CES distributions with heavy tails. These attributes will be demonstrated through numerical examples, in terms of computational time and the estimation error. An application in DOA estimation with MUSIC spectrum is also presented.

In recent years the convergence behavior of random node asynchronous graph communications have been studied for the case of undirected graphs. This paper extends these results to the case of graphs having arbitrary directed edges possibly with a non-diagonalizable adjacency matrix. Assuming that the graph operator has eigenvalue 1 and the input signal satisfies a certain condition (which ensures the existence of fixed points), this study presents the necessary and sufficient condition for the mean-squared convergence of the graph signal. The presented condition depends on the graph operator as well as the update probabilities, and the convergence of the randomized asynchronous updates may be achieved even when the underlying operator is not stable in the synchronous setting. As an application, the node-asynchronous updates are combined with polynomial filtering in order to obtain a spectral clustering for directed networks. The convergence is also verified with numerical simulations.

A new type of beamspace for array processing is introduced called convolutional beamspace. It enjoys the advantages of traditional beamspace such as lower computational complexity, increased parallelism of subband processing, and improved resolution threshold for DOA estimation. But unlike traditional beamspace methods, it allows root-MUSIC and ESPRIT to be performed directly for ULAs without any overhead of preparation, as the Vandermonde structure and the shift-invariance are preserved under the transformation. The method produces more accurate DOA estimates than traditional beamspace methods, and for correlated sources it produces better estimates than element-space methods.

Ramanujan filter banks have been used for identifying periodicity structure in streaming data. This letter studies the locations of zeros of Ramanujan filters. All the zeros of Ramanujan filters are shown to lie on or inside the unit circle in the z-plane. A convenient factorization appears as a corollary of this result, which is useful to identify common factors between different Ramanujan filters in a filter bank. For certain families of Ramanujan filters, further structure is identified in the locations of zeros of those filters. It is shown that increasing the number of periods of Ramanujan sums in the filter definition only increases zeros on the unit circle in z-plane. A potential application of these results is that by identifying common factors between Ramanujan filters, one can obtain efficient implementations of Ramanujan filter banks (RFB) as demonstrated here.

In array processing, minimum redundancy arrays (MRA) can identify up to O(N2) uncorrelated sources (the O(N2) property) with N physical sensors, but this property is susceptible to sensor failures. On the other hand, uniform linear arrays (ULA) are robust, but they resolve only O(N) sources. Recently, the robust MRA (RMRA) was shown to possess the O(N2) property and to be as robust as ULA. But finding RMRA is computationally difficult for large N. This paper proposes a novel array geometry called the composite Singer array, which is related to a classic paper by Singer in 1938, and to other results in number theory. For large N, composite Singer arrays could own the O(N2) property and are as robust as ULA. Furthermore, the sensor locations for the composite Singer array can be readily computed by the proposed recursive procedure. These properties will also be demonstrated by using numerical examples.

This paper considers a node-asynchronous implementation of rational ("IIR") filters on graphs, in which the nodes are assumed to wake up randomly and independently from each other, and communicate only with their immediate neighbors. The underlying graph is allowed to be directed, possibly with a non-diagonalizable adjacency matrix. Since the nodes are allowed to act independently, the proposed implementation is practical for very large or autonomous networks where synchronization is difficult to achieve. Furthermore, the proposed algorithm is 1-hop localized on the graph irrespective of the order of the filter. The method is shown to converge in the mean-squared sense under a boundedness assumption on the filter as well as the graph operator. The result follows from the convergence of a more general randomized asynchronous state recursion, which is also presented in this paper. The algorithm is simulated on a random geometric graph, which numerically verifies the convergence.

Sparse arrays can identify O(N2) uncorrelated sources using N physical sensors. This property is because the difference coarray, defined as the differences between sensor locations, has uniform linear array (ULA) segments of length O(N2). It is empirically known that, for sparse arrays like minimum redundancy arrays, nested arrays, and coprime arrays, this O(N2) segment is susceptible to sensor failure, which is an important issue in practical systems. This paper presents the (k-)essentialness property, which characterizes the combinations of the failing sensors that shrink the difference coarray. Based on this, the notion of fragility is proposed to quantify the reliability of sparse arrays with faulty sensors, along with comprehensive studies of their properties. It is demonstrated through examples that there do exist sparse arrays that are as robust as ULA and at the same time, they enjoy O(N2) consecutive elements in the difference coarray.

This paper considers an autonomous network in which the nodes communicate only with their neighbors at random time instances, repeatedly and independently. Polynomial graph filters studied in the context of graph signal processing are inadequate to analyze signals on this type of networks. This is due to the fact that the basic shift on a graph requires all the nodes to communicate at the same time, which cannot be assumed in an autonomous setting. In order to analyze these type of networks, this paper studies an asynchronous power iteration that updates the values of only a subset of nodes. This paper further reveals the close connection between asynchronous updates and the notion of smooth signals on the graph. The paper also shows that a cascade of random asynchronous updates smooths out any arbitrary signal on the graph.

If the sampled version x(n)=xc(nT) of a continuous-time signal xc(t) is periodic, it does not necessarily imply that xc(t) is periodic. This paper presents some conditions under which periodicity of xc(t) is indeed implied. The conditions for this implication are more relaxed than bandlimitedness. The results place in evidence a multriate method to estimate the period of xc(t) from the samples x(n). The method works better than DFT based methods when the available data segment is short and multiple hidden periods are to be estimated.

One-bit quantization has become an important topic in massive MIMO systems, as it offers low cost and low complexity in the implementation. Techniques to achieve high performance in spite of the coarse quantizers have recently been advanced. In the context of array processing and direction-of-arrival (DOA) estimation also, one bit quantizers have been studied in the past, although not as extensively. This paper shows that sparse arrays such as nested and coprime arrays are more robust to the deleterious effects of one-bit quantization, compared to uniform linear arrays (ULAs); in fact, sparse arrays with one-bit quantizers are often found to be as good as ULAs with unquantized data. Nested and coprime arrays without quanitzers are known to be able to resolve more DOAs than the number of sensors, when sources are uncorrelated. It will be demonstrated that this continues to be true even with one-bit quantization.

In order to analyze signals defined over graphs, many concepts from the classical signal processing theory have been extended to the graph case. One of these concepts is the uncertainty principle, which studies the concentration of a signal on a graph and its graph Fourier basis (GFB). An eigenvector of a graph is the most localized signal in the GFB by definition, whereas it may not be localized in the vertex domain. However, if the eigenvector itself is sparse, then it is concentrated in both domains simultaneously. In this regard, this paper studies the necessary and sufficient conditions for the existence of 1, 2, and 3-sparse eigenvectors of the graph Laplacian. The provided conditions are purely algebraic and only use the adjacency information of the graph. Examples of both classical and real-world graphs with sparse eigenvectors are also presented.

Given that a sequence x(n) is periodic with period P belonging to a known integer set {P1, P2, ... PL}, what is the minimum number of samples of x(n) required to find the period? For the special case where the samples of x(n) are constrained to be contiguous in time, this problem has recently been solved. More generally, when the samples are allowed to be non-contiguous, the problem is quite difficult. This paper provides the answer for the restricted situation where P ∈ {P1, P2}. With P12, the necessary and sufficient number of (possibly noncontiguous) samples for period estimation turns out to be (a) P1, if P1is not a divisor of P2, and (b) P2otherwise. While the proof is quite involved even in this restricted case, it is likely to form the basis for addressing the more general situation where P ∈ {P1, P2, ... PL}.

Ramanujan filter banks (RFB) are useful to generate time-period plane plots which allow one to localize multiple periodic components in the time domain. For such applications, the RFB produces more satisfactory results compared to short time Fourier transforms and other conventional methods, as demonstrated in recent years. This paper introduces a novel multiplier-less, hence computationally very efficient, structure to implement Ramanujan filter banks, based on a new result connecting Ramanujan sums and natural periodic bases.

In problems involving the optimization of atomic norms, an upper bound on the dual atomic norm often arises as a constraint. For the special case of line spectral estimation, this upper bound on the dual atomic norm reduces to upper-bounding the magnitude response of a finite impulse response filter by a constant. It is well known that this can be rewritten as a semidefinite constraint, leading to an elegant semidefinite programming formulation of the atomic norm minimization problem. This result is a direct consequence of some classical results in system theory, well known for many decades. This is not detailed in the literature on atomic norms, quite understandably, because the emphasis therein is different. In fact, these connections can be found in the book by B. A. Dumitrescu, cited widely in the atomic norm literature. However, they are spread out among many different results and formulations. This letter makes the connection more clear by appealing to one simple result from system theory, thereby making it more transparent to wider audience.

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 (MRAs), have reduced mutual coupling compared to uniform linear arrays (ULAs). With N denoting the number of sensors, these sparse arrays offer O(N2) freedoms for source estimation because their difference coarrays have O(N2)-long ULA segments. These arrays have different shortcomings: coprime arrays have holes in the coarray, MRAs have no closed-form expressions, and nested arrays have relatively large mutual coupling. 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 reduces mutual coupling significantly. 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 separation λ/2 is significantly reduced. Many theoretical properties are proved and simulations are included to demonstrate the superior performance of these arrays.

Signal processing on graphs finds applications in many areas. Motivated by recent developments, this paper studies the concept of spectrum folding (aliasing) for graph signals under the downsample-then-upsample operation. In this development, we use a special eigenvector structure that is unique to the adjacency matrix of M-block cyclic matrices. We then introduce M-channel maximally decimated filter banks. Manipulating the characteristics of the aliasing effect, we construct polynomial filter banks with perfect reconstruction property. Later we describe how we can remove the eigenvector condition by using a generalized decimator. In this study graphs are assumed to be general with a possibly non-symmetric and complex adjacency matrix.

Coprime arrays, consisting of two uniform linear arrays whose inter-element separations are coprime, can resolve O(MN) sources using only O(M + N) sensors. However, holes in the coarray prevent us from using the full coarray in the MUSIC algorithm for DOA estimation. Through interpolation, it may be possible to use the remaining elements of the coarray to increase the degrees of freedom beyond what is captured in the contiguous ULA section in the coarray. Techniques like positive definite Toeplitz completion, array interpolation, and sparse recovery, manage to include all the information in the coarray, but they demand extra fine-tuned parameters and have individual drawbacks. In this paper, a simple and tractable convex framework via nuclear norm minimization is presented. This approach has no extra tuning parameters and overcomes several undesired issues of other techniques. Numerical examples indicate that, in many instances, the proposed method not only increases the estimation accuracy but also distinguishes more sources than other methods1.

Tandem repeats are periodic segments in the DNA. They play an important role in forensics, tracing population evolution, genetic disorders and so on. Locating them in long DNA sequences is the problem addressed in this paper. A new technique is presented, based on the recently proposed Ramanujan Filter Bank (RFB). The RFB was shown to offer several advantages over the traditional period estimation techniques in DSP, such as those based on spectral estimation (STFT etc.). It involves simple integer operations, and detects several new repeats that could not be identified by popular existing techniques.1 Project Website: see [16].

We address the following question in this paper: Given that the period of a discrete time periodic signal belongs to a set P = {P1, P2,..., Pκ}, what is the minimum duration of the signal necessary to identify its period? It will be shown that the following number of samples is both necessary and sufficient: max Pi+ Pj- gcd (Pi, Pj), where gcd is the greatest common divisor, and the maximization is over all pairs Pi, Pj ∈ P. Sufficiency is shown via a constructive proof, leading to a new period estimation algorithm.

This paper extends the use of coprime arrays and samplers for the case of moving sources. Space-time adaptive processing (STAP) plays an important role in estimating direction-of-arrivals (DOAs) and radial velocities of emitting sources. However, the detection performance is fundamentally limited by the array geometry and the temporal samplers at each sensor. Coprime arrays and coprime samplers offer an enhanced degree of freedom of O(MN) using only O(M + N) physical sensors or samples. In this paper, we propose coprime joint angle-Doppler estimation (coprime JADE), which incorporates both coprime arrays and coprime samplers with the STAP framework. Nonuniform time samples at different sensors can be used to generate a sampled autocorrelation matrix, from which we compute a spatial smoothed matrix. It will be proved that spatial smoothed matrices can be used in the MUSIC algorithm for parameter estimation. With sufficient snapshots, coprime JADE distinguishes O(M1N1M22) independent sources if it corresponds to coprime arrays and coprime samplers with coprime integers (M1;1) and (M2;N2), respectively. It is verified through simulations that coprime JADE resolves the angle-Doppler information better compared to other conventional algorithms.

Coprime DFT filter banks (coprime DFTFB) achieve the effect of an MN-DFTFB by using two DFTFBs of size only M and N, where M and N are coprime integers. However, coprime DFTFBs need to be designed properly, to avoid unwanted bumps in stopbands or unsatisfactory total spectrum coverage, quantified by overall amplitude responses. In this paper, a detailed theoretical analysis will be made on the tradeoffs between bumps and overall amplitude responses. It will be shown that the bump level at the center frequency fbof a bump, is approximately one-fourth of the overall amplitude response at fb. Then, a novel design will be introduced based on an optimization problem pertaining to overall amplitude responses. The original problem is relaxed to a computationally tractable optimization program, which can be solved with alternating minimization algorithms. It is verified with simulations that the new designs cover the spectrum completely.

We propose a new filter-bank structure for the estimation and tracking of periodicities in time series data. These filter-banks are inspired from recent techniques on period estimation using high-dimensional dictionary representations for periodic signals. Apart from inheriting the numerous advantages of the dictionary based techniques over conventional period-estimation methods such as those using the DFT, the filter-banks proposed here expand the domain of problems that can be addressed to a much richer set. For instance, we can now characterize the behavior of signals whose periodic nature changes with time. This includes signals that are periodic only for a short duration and signals such as chirps. For such signals, we use a time vs period plane analogous to the traditional time vs frequency plane. We will show that such filter banks have a fundamental connection to Ramanujan Sums and the Ramanujan Periodicity Transform.

It is well-known that the Ramanujan-sum cq(n) has applications in the analysis of periodicity in sequences. Recently the author developed a new type of Ramanujan-sum representation especially suited for finite duration sequences x(n): This is based on decomposing x(n) into a sum of signals belonging to so-called Ramanujan subspaces Sqi. This offers an efficient way to identify periodic components using integer computations and projections, since cq(n) is integer valued. This paper revisits multidimensional signals with periodicity on possibly nonseparable integer lattices. Multidimensional Ramanujan-sum and Ramanujan-subspaces are developed for this case. A Ramanujan-sum based expansion for multidimensional signals is then proposed, which is useful to identify periodic components on nonseparable lattices.

Sparse arrays such as nested and coprime arrays use a technique called spatial smoothing in order to successfully perform MUSIC in the difference-coarray domain. In this paper it is shown that the spatial smoothing step is not necessary in the sense that the effect achieved by that step can be obtained more directly. In particular, with R̃ssdenoting the spatial smoothed matrix with finite snapshots, it is shown here that the noise eigenspace of this matrix can be directly obtained from another matrix R̃ which is much easier to compute from data.

Traditionally, most of the analysis of discrete time multidimensional periodicity in DSP is based on defining the period as a parallelepiped. In this work, we study whether this framework can incorporate signals that are repetitions of more general shapes than parallelepipeds. For example, the famous Dutch artist M. C. Escher constructed many interesting shapes such as fishes, birds and animals, which can tile the continuous 2-D plane. Inspired from Escher's tilings, we construct discrete time signals that are repetitions of various kinds of shapes. We look at periodicity in the following way - a given shape repeating itself along fixed directions to tile the entire space. By transcribing this idea into a mathematical framework, we explore its relationship with the traditional analysis of periodicity based on parallelepipeds. Our main result is that given any such signal with an arbitrarily shaped period, we can always find an equivalent parallelepiped shaped period that has the same number of points as the original period.

The problem of parameter identifiability in linear underdetermined models is addressed, where the observed data vectors follow a multivariate Gaussian distribution. The problem is underdetermined because the dimension of parameters characterizing the distribution of the data is larger than the dimension of the observed vectors. Such models arise frequently in Bayesian Compressive sensing and Sparse Bayesian Learning problems, where the parameter vector to be estimated, is assumed to be sparse. We establish explicit conditions for parameter identifiability in such models, by relating the ambient dimension of the hyperparameter space and that of the data. We establish a crucial result that in such underdetermined models, even without requiring the parameter to be sparse, it is possible to guarantee unique identifiability of the parameters as long as these two dimensions satisfy a certain condition. When such a condition is violated, the unconstrained statistical model is no more identifiable and additional constraints in the form of sparsity need to be enforced to recover the true parameter.

Ramanujan sums have in the past been used to represent arithmetic sequences. It is shown here that for finite duration (FIR) sequences with length N, the traditional representation is not suitable. Two new types of Ramanujan-sum expansions are proposed here for the FIR case, each offering an integer basis. One of these is particularly suited to identify periodicities in the FIR sequence. This representation in fact expresses any FIR sequence as a sum of orthogonal sequences each with a hidden periodicity corresponding to a divisor of N.

A finite duration sequence exhibiting periodicities does not in general admit a sparse representation in terms of the DFT basis unless the period is a divisor of the duration. This paper develops a dictionary called the Farey dictionary for the efficient representation of such sequences. It is shown herein that this representation is especially useful for identifying hidden periodicities in a finite data record. The properties of the Farey dictionary are studied, and the dictionary is shown to be superior to the conventional DFT based uniform dictionary, from the view point of identifying hidden periods.

The problem of direction of arrival (DOA) estimation of narrowband sources using an antenna array is considered where the number of sources can potentially exceed the number of sensors. In earlier works, the authors showed that using a suitable antenna geometry, such as the nested and coprime arrays, it is possible to localize O(M2) sources using M sensors. To this end, two different approaches have been proposed. One is based on an extension of subspace based methods such as MUSIC to these sparse arrays, and the other employs l1 norm minimization based sparse estimation techniques by assuming an underlying grid. While the former requires the knowledge of number of sources, the latter suffers from basis mismatch effects. In this letter, a new approach is proposed which overcomes both these weaknesses. The method is hybrid in nature, using a low rank matrix denoising approach followed by a MUSIC-like subspace method to estimate the DOAs. The number of sources is revealed as a by-product of the low rank denoising stage. Moreover, it does not assume any underlying grid and thereby does not suffer from basis mismatch. Numerical examples validate the effectiveness of the proposed method when compared against existing techniques.

Consider a multiple measurement vector (MMV) model given by y[n] = Axs[n]; 1 ≤ n ≤ L where equation denote the L measurement vectors, A ∈ RM×Nis the measurement matrix and xs[n] ∈ RNare the unknown vectors with same sparsity support denoted by the set S0with |S0| = D. It has been shown in a recent paper by the authors that when the elements of xs[n] are uncorrelated from each other, one can recover sparsity levels as high as O(M2) for suitably designed measurement matrix. The recovery is exact when support recovery algorithms are applied on the ideal correlation matrix. When we only have estimates of the correlation, it is still possible to probabilistically argue the recovery of sparsity levels (using a coherence based argument) that is much higher than that guaranteed by existing coherence based results. However the lower bound on the probability of success is found to increase rather slowly with L (as 1-C/L for some constant C > 0) without any further assumption on the distribution of the source vectors. In this paper, we demonstrate that when the source vectors belong to a Gaussian distribution with diagonal covariance matrix, it is possible to guarantee the recovery of original support with overwhelming probability. We also provide numerical simulations to demonstrate the effectiveness of the proposed strategy by comparing it with other popular MMV based methods.

This paper addresses the joint design problem of bit allocation and decision feedback equalizer (DFE) transceiver for multi-input multi-output (MIMO) broadcast (BC) channels. Channel state information (CSI) is assumed to be available both at the transmitter and receivers. The transceiver is designed by minimizing maximum symbol error rate (MAX-SER) under the total power and bitrate constraints. The bit allocation, precoder, feed-forward matrices and feedback matrices are the optimization variables. For the two-user case, a particular class of joint triangularization (JT) can be applied to obtain the optimal design for the problem, which is the optimal JT minimum Max-SER BC DFE transceiver (JTMMS). For arbitrary number of users, the suboptimal design, the QR BC DFE transceiver with bit allocation, is discussed. In the simulations, the Max-SER and average BER performance of the proposed systems are investigated.

This paper considers the decomposition of a complex matrix as the product of several sets of semi-unitary matrices and upper triangular matrices in iterative manner. The innermost triangular matrix has its diagonal elements equal to the geometric mean of the singular values of the complex matrix. This decomposition, generalized geometric mean decomposition (GGMD), has one order less complexity than the geometric mean decomposition (GMD) if the target matrix is a diagonal matrix. GGMD can be used to design the optimal decision feedback equalizer (DFE) MMSE transceiver for arbitrary multi-input-multi-output (MIMO) channels. The GGMD transceiver shares the same performance as the transceiver designed by using GMD. For the applications over cyclic prefix system, the GGMD transceiver has K/ log2(K) times lower complexity1than the GMD transceiver, where K is the number of subchannels and is a power of 2.

In this paper, we develop the theory of a new class of two dimensional arrays with sensors on lattice(s) which can be used to construct a virtual array of much larger size through passive processing. This structure is obtained by systematically nesting two arrays, one with sensors suitably placed on a sparse lattice and the other on an appropriately chosen dense lattice. The difference co-array of such an array with M and N elements respectively on the two lattices, is proved to be a larger two dimensional array with O(MN) sensors present contiguously (without holes) on the dense lattice. It will be shown that there is complete freedom to choose the sparse and dense arrays as long as they are related by an integer matrix (which can also be arbitrarily chosen). To exploit the increased degrees of freedom offered by the array for two dimensional DOA estimation of more sources than sensors, a novel algorithm based on the concept of two dimensional spatial smoothing is also proposed. The validity of the proposed methods is verified through numerical examples.

Sparse sampling with coprime lattice arrays was introduced recently in the literature. It has been shown that a dense coarray can be constructed from such a pair of arrays, and is useful in array processing and image processing applications. For example, the coarray allows one to identify many more sources than sensors. After a brief review of these fundamentals, this paper examines the case where the two arrays are generated by matrices that are adjugates of each other. In this case it is possible to obtain a dense rectangular tiling of the 2D frequency plane from a pair of coarse 2D DFT filter banks. The special case where the adjugate pairs are generated by skew circulant matrices has some advantages, which are examined in detail.

Filter bank optimization for specific input statistics has been of great interest in both theory and practice in many signal processing applications. In this paper we consider biorthogonal GTD (generalized triangular decomposition) filter banks for optimizing the coding gain. We develop some theoretical results for the optimal biorthogonal GTD subband coder. We also show in both theory and numerical simulations that biorthogonal GTD subband coders have superior performance than biorthogonal subband coders, orthonormal GTD subband coders, and orthonormal subband coders. In addition, the uniform bit loading scheme can with no loss of optimality be used in the optimal biorthogonal GTD coders, which does not have the granularity problem arising in the conventional optimum bit loading formula.

Commuting coprime integer matrices arise in signal processing in a number of contexts. This paper develops two ways, one nonlinear and the other linear, to generate new commuting coprime pairs from known pairs. The first method is based on computing powers of the initial pair of matrices, and the second method is based on appropriate types of linear combinations of the initial pair of matrices. This enriches the already known families of coprime matrices reported in recent literature. Several properties of the newly generated coprime pairs are also addressed.

We consider the design of MIMO transceivers with zero-forcing (ZF) decision feedback detection over time-varying MIMO channels. The data vectors are grouped into spacetime blocks (ST-blocks) for the spatial and temporal precoding to take advantage of the diversity offered by time-varying channels. We extend the generalized triangular decomposition (GTD) for the case of time-varying channels by introducing the space-time GTD (ST-GTD). Based on ST-GTD and the channel prediction, we propose the space-time geometric mean decomposition (ST-GMD) based system which minimizes the arithmetic mean square error (MSE) for every ST-block. We also present the causal ST-GTD based system which does not require channel prediction. The simulations show that this system achieves the same BER performance asymptotically as the ST-GMD based system. In moderate high SNR, the proposed systems have superior BER performance over the conventional GMD-based systems.

A novel array structure for significantly increasing the degrees of freedom of linear arrays is proposed. This structure is obtained by systematically nesting two or more uniform linear arrays and can provide O(N2) degrees of freedom using only O(N) physical sensors. It is possible to provide closed form expressions for the sensor locations and the exact degrees of freedom obtainable from the proposed array as a function of the total number of sensors. This cannot be done for existing classes of arrays like minimum redundancy arrays which have been used earlier for detecting more sources than sensors. A novel spatial smoothing based technique is also proposed to exploit the increased degrees of freedom offered by the array to perform DOA estimation of more sources than sensors, using only second order statistics of the received data. This method does not suffer from inherent weaknesses of techniques employing higher order statistics or quasi stationarity of sources. The validity of all the proposed methods is verified through numerical examples.

In the class of systems with linear precoder and zero-forcing (ZF) DFE for zero-padded MIMO frequency selective channels, existing optimal transceiver designs present two major drawbacks. First, the optimal system requires a large number of bits to encode the full precoding matrix. Second, the full precoding matrix leads to complex computations. These disadvantages become more severe as bandwidth (BW) efficiency increases. In this article, we propose using the block diagonal geometric mean decomposition (BD-GMD) technique to design an alternative transceiver. The proposed ZF-BD-GMD system uses a block diagonal orthogonal precoder matrix structure to reduce the required number of encoding bits and simplifies the computation. While solving the current optimal system's drawbacks, the ZF-BD-GMD system also produces a similar bit error rate (BER) performance when the block size is large. In other words, the ZF-BD-GMD system is asymptotically optimal in the class of communication systems with linear precoder and ZF-DFE receiver.1

This paper considers the DFE transceiver optimization for time-varying memoryless MIMO channels under zero-forcing (ZF) constraint. For time-varying channels, the uncoded average BER of the conventional geometric mean decomposition (GMD) based systems is not minimized because of the diverse arithmetic MSEs at different block times. To minimize the BER, a new GMD transceiver is proposed, in which the data vectors are grouped into space-time blocks (ST-blocks). A channel independent-temporal precoder is superimposed on the conventional blockwise GMD for the equalization of arithmetic MSEs across different blocks. So, the proposed system can take advantage of both the temporal and spatial diversity offered by time-varying MIMO channels. At moderate high SNR, corresponding to reasonable BER, there exists a class of optimal channel-independent temporal precoders, e.g., DFT and Hadamard matrices, for the minimization of average BER. Furthermore, simulation results show that the average BER performance of the proposed system improves with ST-block size and converges at moderate ST-block size.

A novel approach to beamforming using a new class of sensor arrays is proposed, which can increase the achievable degrees of freedom significantly beyond the conventional limits obtained from uniform linear arrays (ULA). This class of arrays is named as "nested arrays" since they are obtained by nesting two or more ULAs with increasing inter-sensor spacing. Using the second order statistics of the signal received by such an array in a novel way, it is possible to perform beamforming with O(N2) de grees of freedom using only O(N) physical elements. This kind of beamforming will be shown to be essentially non linear in nature and theoretically, it is capable of nulling the effect of noise provided enough snapshots are available.

The interpolated FIR (IFIR) radar was recently introduced in the context of MIMO radar theory. It was shown that this system has a signal to clutter ratio intermediate between those of the SIMO and MIMO radars. This paper considers the optimal design of the active IFIR beamformer in presence of jammers. It is shown that this beamformer can achieve beamwidths as sharp as those of colocated MIMO radars with full-length virtual arrays. At the same time, the extra complexity of MIMO radars, which arises from use of multiple transmitter waveforms and several sets of receiver matched filter banks, is not present in the IFIR realization. Design examples for IFIR radars which optimize the receiver beamforming weights in presence of jammers for fixed transmitter are also presented.

Given a continuous time LTI system with impulse response hc(t), it is shown that the uniformly spaced samples hc(nT) can be identified for any chosen spacing T by using an impulse train input with an arbitrarily small rate 1/NT and sampling the system output with an arbitrarily small rate 1/MT , provided M and N are coprime. This idea, referred to here as the sparse coprime sensing method for system identification, is closely related to well known results in multirate signal processing. It is shown that the problem can be related to the identification of a decimation filter from input-output measurements. It is also shown that the problem is equivalent to the identification of a discrete time N × M LTI system from a knowledge of the full rate input and output vector sequences.

The geometric mean decomposition (GMD) transform coder (TC) was recently introduced and was shown to achieve the optimal coding gain without bit loading under the high bit rate assumption. However, the performance of the GMD transform coder is degraded in the low rate case. There are mainly two reasons for this degradation. First, the high bit rate quantizer model becomes invalid. Second, the quantization error is no longer negligible in the prediction process when the bit rate is low. In this letter, we introduce dithered quantization to tackle the first difficulty, and then redesign the precoders and predictors in the GMD transform coders to tackle the second. We propose two dithered GMD transform coders: the GMD subtractive dithered transform coder (GMD-SD) where the decoder has access to the dither information and the GMD nonsubtractive dithered transform coder (GMD-NSD) where the decoder has no knowledge about the dither. Under the uniform bit loading scheme in scalar quantizers, it is shown that the proposed dithered GMD transform coders perform significantly better than the original GMD coder in the low rate case.

The concept of MIMO (multiple-input multiple-output) radar allows each transmitting antenna element to transmit an arbitrary waveform. This provides extra degrees of freedom compared to the traditional transmit beamforming approach. It has been shown in the recent literature that MIMO radar systems have many advantages. In this paper, we consider the joint optimization of waveforms and receiving filters in the MIMO radar when the prior information of target and clutter are available. A novel iterative algorithm is proposed to optimize the waveforms and receiving filters such that the detection performance can be maximized. The proposed algorithm guarantees that the SINR performance improves in each iteration step. The numerical results show that the proposed methods have better SINR performances than existing design methods.

Frequency invariant beamforming with sensor arrays is generally achieved using filters in the form of tapped delay-lines following each sensor. However it has been recently shown that with the help of the rectangular smart antenna array, it is possible to generate frequency invariant beampattern without using filters. In this paper, this frequency invariant beamforming technique is utilized to perform MVDR beamforming in the beamspace by designing frequency invariant beams spanning the desired range of azimuthal angles and optimally combining them. However, the performance of the frequency invariant beamformer depends on the number of sensors which could be large for a rectangular array of size M times N. Making use of the virtual array concept used in MIMO radar, a novel method of producing the same frequency invariant beam, using only M transmitting and N receiving antennas, is proposed and a design example is provided to demonstrate the idea.

We consider new optimization problems for transceivers with DFE receivers and linear precoders, which also use bit loading at the transmitter. First, we consider the MIMO QoS (quality of service) problem, which is to minimize the total transmitted power when the bit rate and probability of error of each data stream are specified. The developments of this paper are based on the generalized triangular decomposition (GTD) recently introduced by Jiang, Li, and Hager. It is shown that under some multiplicative majorization conditions there exists a custom GTD-based transceiver which achieves the minimal power. The problem of maximizing the bit rate subject to the total power constraint and given error probability is also considered in this paper. It is shown that the GTD-based systems also give the optimal solutions to the bit rate maximization problem.

In this paper we consider the optimization of transceivers which use the nonlinear vector perturbation technique at the transmitter. Since the perturbation vector can be almost totally removed at the receiver, the transmitter can use this extra freedom to reduce the transmitted power while maintaining the performance. The two cases considered in this paper are linear transceivers and transceivers with decision feedback (DFE). For both cases, efficient iterative power loading algorithms are developed to reduce the average bit error rate under the total transmitted power constraint. We present simulation results showing that the proposed technique performs better than the existing state-of-the-art uniform channel decomposition (UCD) system and the vector perturbation (VP) precoder.

There have been many results on designing transceivers for MIMO channels. In early results, the transceiver is designed for a given bit allocation. In this paper we will jointly design the transceiver and bit allocation for maximizing bit rate. By using a high bit rate assumption, we will see that the optimal transceiver and bit allocation can be obtained in a closed form using simple Hadamard inequality and the Poincare separation theorem. In the simulation, we will demonstrate the usefulness of the joint design. Simulation results, in which a high bit rate assumption is not used in allocating bits, show that a higher bit rate can be achieved compared to previously reported methods.

MIMO (multiple-input multiple-output) radar is an emerging technology which has drawn considerable attention. Unlike the traditional SIMO (single-input multiple-output) radar, which transmits scaled versions of a single waveform in the antenna elements, the MIMO radar transmits independent waveforms in each of the antenna elements. It has been shown that MIMO radar systems have many advantages such as high spatial resolution, improved parameter identifiability, and enhanced flexibility for transmit beampattern design. In the traditional SIMO radar, the range and Doppler resolutions can be characterized by the radar ambiguity function. It is a major tool for studying and analyzing radar signals. Recently, the ambiguity function has been extended to the MIMO radar case. In this paper, some mathematical properties of the MIMO radar ambiguity function are derived. These properties provide insights into the MIMO radar waveform design.

In this paper we propose a method for joint optimization of transceivers with fractionally spaced equalization (FSE). We use the effective single-input multiple-output (SIMO) model for the fractionally spaced receiver. Since the FSE is used at the receiver, the optimized precoding scheme should be changed correspondingly. Simulation shows that the proposed method demonstrates remarkable improvement for jointly optimal linear transceivers as well as transceivers with decision feedback.

The multiple-input multiple-output (MIMO) radar concept has drawn considerable attention recently. In the traditional single-input multiple-output (SIMO) radar system, the transmitter emits scaled versions of a single waveform. However, in the MIMO radar system, the transmitter transmits independent waveforms. It has been shown that the MIMO radar can be used to improve system performance. Most of the MIMO radar research so far has focused on the uniform array. However, it is in general a loss of optimality to assume the array to be uniform. In this paper, the nonuniform array design problem in the MIMO radar is studied. In the SIMO radar, it has been shown that there is a class of linear arrays which minimizes the number of redundant spacings in the array. These are called minimum redundancy linear arrays. It has been shown that this class of arrays has excellent performance in rejection of mainlobe interferences. In this paper, the idea of minimum redundancy linear array is extended to the MIMO radar case. The numerical examples show that the proposed minimum redundancy MIMO radar results in improved rejection of mainlobe interferences, with negligible degradation in sidelobe interference rejection capabilities.

In orthogonal frequency division multiplexing (OFDM) systems, symbol synchronization is a critical step for successful data transmission. While this task is done in most current systems by using training symbols, a few studies have been dedicated to solving the problem blindly, that is, where training symbols are not available. Blind symbol synchronization problem is especially important in many blind channel estimation algorithms in the literature which assume that OFDM symbol synchronization is perfect. In this paper, a broader version of the blind symbol synchronization problem is studied, namely, blind block synchronization in cyclic-prefix (CP) systems. The proposed algorithm for this broader problem covers the blind symbol synchronization problem in OFDM systems. Unlike previously reported algorithms which are based on obtaining sufficient statistics of received samples, the proposed algorithm is capable of identifying the correct block boundaries using much less received data in absence of noise. Simulation results of the proposed algorithm not only verify the declared property but also demonstrate improvement in accuracy of symbol synchronization over previously reported algorithms in presence of noise.

In the traditional transmitting beamforming radar system, the transmitting antennas send coherent waveforms which form a highly focused beam. In the MIMO radar system, the transmitter sends noncoherent (possibly orthogonal) broad (possibly omnidirectional) waveforms. These waveforms can be extracted by a matched interbank. The extracted signals can be used to obtain more diversity or improve the clutter resolution. In this paper, we focus on space-time adaptive processing (STAP) for MIMO radar systems which improves the clutter resolution. With a slight modification, STAP methods for the SIMO radar case can also be used in MIMO radar. However, in the MIMO radar, the rank of the jammer-and-clutter subspace becomes very large, especially the jammer subspace. It affects both the complexity and the convergence of the STAP. In this paper, a new subspace method is proposed. It computes the clutter subspace using the geometry of the problem rather than data and utilizes the block diagonal property of the jammer covariance matrix. Because of fully utilizing the geometry and the structure of the covariance matrix, the method is very effective for STAP in MIMO radar.

Blind channel identification using linear redundant filterbank precoders (LRP) has been studied extensively in the literature. Most methods are proposed based on the assumption that block synchronization is perfect. In practice, a blind block synchronization algorithm must be used to justify this assumption. This paper studies the blind block synchronization problem in systems using a zero-padding (ZP) precoder. A previously reported method is reviewed and a new approach for the problem is proposed. Generalized versions of both approaches are then developed using a parameter called repetition index. Simulation results show that when the repetition index is chosen to be greater than unity, the block synchronization error rate performance of the proposed algorithm has a significant improvement over the previously reported method.

Power-symmetric IIR filters have in the past been used in two-channel filter banks. If appropriately designed, such filters have allpass polyphase components, and this induces useful properties in the filter bank. For example, IIR orthonormal filter banks have in the past been designed in this way, and generate orthonormal basis functions. In this paper we study some theoretical properties of IIR power symmetric filters in a more general perspective. This includes the derivation of a general analytical form, and a study of pole locations.

Recently, profile context-sensitive HMMs (profile-csHMMs) have been proposed which are very effective in modeling the common patterns and motifs in related symbol sequences. Profile-csHMMs are capable of representing long-range correlations between distant symbols, even when these correlations are entangled in a complicated manner. This makes profile-csHMMs an useful tool in computational biology, especially in modeling noncoding RNAs (ncRNAs) and finding new ncRNA genes. However, a profile-csHMM based search is quite slow, hence not practical for searching a large database. In this paper, we propose a practical scheme for making the search speed significantly faster without any degradation in the prediction accuracy. The proposed method utilizes a pre-screening filter based on a profile-HMM, which filters out most sequences that will not be predicted as a match by the original profile-csHMM. Experimental results show that the proposed approach can make the search speed eighty times faster.

Recently, a new subspace-based blind channel estimation algorithm in cyclic prefix (CP) system was reported. A persistency of excitation (PE) property of the input signal is required for the algorithm to work. In this paper, the probability of fulfilling the PE property under different situations is studied. Four factors in the algorithm affect the PE property of the input signal: 1) signal constellation used; 2) precoder coefficients; 3) number of consecutive blocks; 4) a number called the repetition index. Theoretical derivations as well as numerical simulations are given to demonstrate the main points of this paper. Important conclusions are 1) that the probability of fulfilling the PE property increases and converges to unity when the number of received blocks increases but is always upper-bounded by a value less than unity when the repetition index increases; 2) that the probability of fulfilling the PE property is smaller when the algorithm is applied in orthogonal frequency division multiplexing (OFDM) systems than in single-carrier-cyclic-prefix (SC-CP) systems.

MIMO channels and wireless communications systems have generated a great deal of renewed interest in linear system theory. This paper presents two results. The first is a simple proof based on first principles, of the known fact that the McMillan degree of a causal M times M MIMO system is at least as large as the degree of its determinant. The second is a new result which shows that the degree of the M x M system z-1G(z) is equal to the degree of G(z) plus M if and only if the causal system G(z) has an anticausal inverse.

In communication systems which used filter bank precoders with zero padding (ZP) at the transmitter, the effect of an FIR channel can be equalized without the use of IIR equalizers. In this paper a number of observations are made with regard to the noise gain created by the equalizer at the receiver. If the number of received samples per block actually utilized in equalization is reduced to the number of transmitted samples per block, then the noise gain can be very large for channels with zeros outside the unit circle. As the number of utilized received samples increases the situation improves. Most importantly, it is shown that when all the redundant samples in each block are utilized for estimation of transmitted symbols then the noise gain is not sensitive to whether the channel zeros are inside, on, or outside the unit circle, and depends only on the FIR channel autocorrelation

In this letter, we analyze the performance of a recently reported generalized blind channel estimation algorithm. The algorithm has a parameter called repetition index, and it reduces to two previously reported special cases when the repetition index is chosen as unity and as the size of received blocks, respectively. The theoretical performance of the generalized algorithm is derived in high-SNR region for any given repetition index. A recently derived Cramer-Rao bound (CRB) is reviewed and used as a benchmark for the performance of the generalized algorithm. Both theory and simulation results suggest that the performance of the generalized algorithm is usually closer to the CRB when the repetition index is larger, but the performance does not achieve the CRB for any repetition index.

The profile hidden Markov model is a specific type of HMM that is well suited for describing the common features of a set of related sequences. It has been extensively used in computational biology, where it is still one of the most popular tools. In this paper, we propose a new model called the profile context-sensitive HMM. Unlike traditional profile-HMMs, the proposed model is capable of describing complex long-range correlations between distant symbols in a consensus sequence. We also introduce a general algorithm that can be used for finding the optimal state-sequence of an observed symbol sequence based on the given profile-csHMM. The proposed model has an important application in RNA sequence analysis, especially in modeling and analyzing RNA pseudoknots.

The V-BLAST (vertical Bell labs layered space-time) system is one of the MIMO systems designed to achieve a good multiplexing gain. In the recent literature, a V-BLAST precoder has been added in the transmitter which exploits channel information. This precoder forces each symbol stream to have identical MSE (mean square error). It can be viewed as an alternative to the bitloading method. In this paper, this precoded V-BLAST is extended to the case of ISI MIMO channels. Both the FIR and OFDM types of transceivers are derived.

It is well-known that redundant filter bank precoders can be used for blind identification as well as equalization of FIR channels. Several algorithms have been proposed in the literature exploiting trailing zeros in the transmitter. In this paper we propose a generalized algorithm of which the previous algorithms are special cases. By carefully choosing system parameters, we can jointly optimize the system performance and computational complexity. Simulation shows that the proposed algorithm outperforms the previous ones when the parameters are optimally chosen.

There are many ways to define richness of a discrete time signal. This paper considers a particular definition and explores the conditions under which a linear time invariant system preserves the richness property. Several examples are presented to clarify the issues involved in the problem. Some sufficient conditions are presented. Also presented are necessary and sufficient conditions for some special cases. A set of necessary and sufficient conditions for the most general case is not known at this time.

The hidden Markov model is well-known for its efficiency in modeling short-term dependencies between adjacent samples. However, it cannot be used for modeling longer-range interactions between symbols that are distant from each other. In this paper, we introduce the concept of context-sensitive HMM that is capable of modeling strong pairwise correlations between distant symbols. Based on this model, we propose a polynomial-time algorithm that can be used for finding the optimal state sequence of an observed symbol string. The proposed model is especially useful in modeling palindromes, which has an important application in RNA secondary structure analysis.

Recently, much attention has been given to the design of optimal finite impulse response (FIR) compaction filters. Such filters, which arise in the design of optimal signal-adapted orthonormal FIR filter banks, satisfy a magnitude squared Nyquist constraint in addition to the inherent FIR assumption. In this paper, we focus on the least squares optimal design of FIR filters whose magnitude squared response satisfies a Nyquist constraint. Using a complete characterization of such systems in terms of Householder-like building blocks, an iterative gradient based greedy algorithm is proposed to design such filters. Simulation results provided show the merit of the proposed technique for designing FIR compaction filters.

The problem of estimating a signal that is corrupted by additive noise has been of interest to many researchers for practical, as well as theoretical, reasons. Many of the traditional denoising methods use linear methods such as Wiener filtering. Recently, nonlinear methods, especially those based on wavelets, have become increasingly popular, due to a number of advantages over the linear methods. It has been shown that wavelet-thresholding has near-optimal properties in the minimax sense, and guarantees a better rate of convergence, despite its simplicity. Even though much work has been done in the field of wavelet-thresholding, most of it was focused on statistical modeling of the wavelet coefficients and the optimal choice of the thresholds. We propose a custom thresholding function which can improve the denoised results significantly. Simulation results are given to demonstrate the advantage of the new thresholding function.

With the advent of wavelets for lossy data compression came the notion of representing signals in a certain vector space by their projections in well chosen subspaces of the original space. In this paper, we consider the subspace of signals generated by an overdecimated rational nonuniform filter bank and find the optimal conditions under which the mean-squared error between a given deterministic signal and its representation in this subspace is minimized for a fixed set of synthesis filters. Under these optimal conditions, it is shown that choosing the synthesis filters to further minimize this error is simply an energy compaction problem. With this, we introduce the notion of deterministic energy compaction filters for classes of signals. Simulation results are presented showing the merit of our proposed method for optimizing the synthesis filters.

We propose a model based approach for estimation of probability mass functions for discrete random variables. The model is based on tools from multirate signal processing. Similar in principle to the kernel based methods, the approach takes advantage of well-known results from multirate signal processing theory. Similarities to and differences from wavelet based approaches are also indicated where appropriate. In the final form, the probability estimates are obtained by filtering the square root of the histogram through a multirate system whose components are biorthogonal partners of each other.

With the advent of wavelets for lossy data compression came the notion of representing signals in a certain vector space by their projections in well chosen subspaces of the original space. In this paper, we consider the subspace of signals generated by an overdecimated rational nonuniform filter bank and find the optimal conditions under which the mean-squared error between a given deterministic signal and its representation in this subspace is minimized for a fixed set of synthesis filters. Under these optimal conditions, it is shown that choosing the synthesis filters to further minimize this error is simply an energy compaction problem. With this, we introduce the notion of deterministic energy compaction filters for classes of signals. Simulation results are presented showing the merit of our proposed method for optimizing the synthesis filters.

We propose a model based approach for estimation of probability mass functions for discrete random variables. The model is based on tools from multirate signal processing. Similar in principle to the kernel based methods, the approach takes advantage of well-known results from multirate signal processing theory. Similarities to and differences from wavelet based approaches is also indicated where appropriate. In the final form, the probability estimates are obtained by filtering the square root of the histogram through a multirate system whose components are biorthogonal partners of each other.

Two previous contributions discussed the theory of perfect-reconstruction (PR) chromatic derivative filter banks comprising an infinite number of channels. This paper extends the theory to the case of finite channels. A novel time domain procedure is delineated for designing the synthesis filters that achieve PR in this case.

We present a new low-complexity method for the design of channel shortening equalizers for discrete multitone (DMT) modulation systems using the eigenfilter approach. In contrast to other such methods which require a Cholesky decomposition for each delay parameter value used, ours requires only one such decomposition. Simulation results show that our method performs nearly optimally in terms of observed bit rate.

The advent of discrete multitone modulation (DMT) systems in recent years has brought to light the importance of channel shortening equalizers. In this paper, we present a method for the design of one such equalizer for multiple-input multiple-output (MIMO) linear dispersive channels. This method is a generalization of one that was used for shortening of single-input single-output (SISO) channels. Experimental results presented show that our design method performs better than the minimum mean-squared error (MMSE) technique in terms of effective channel energy compaction.1

The cyclic prefix system is widely used for frequency domain equalization in discrete multitone channels. In this paper we show how the idea of fractionally spaced equalization (FSE) can be adapted to cyclic prefix systems. We derive the condition for a perfect FSE, and show that there is a certain freedom in the choice of the equalizer coefficients. This freedom is then exploited to minimize the effect of additive noise at the detector input. The theory is generally applicable to any deconvolution problem, though the setting used for our development uses the language of digital communication.

The concept of fractional biorthogonal partners has been introduced recently by the authors. They arise in many different contexts, one of them being channel equalization with fractionally spaced equalizers. If the amount of oversampling at the receiver is not an integer, but a rational number, the problem of fractionally spaced equalization can be treated using the fractional biorthogonal partner setting. This approach is adopted here. We consider fractionally spaced equalizers with a rational amount of oversampling, show that the FIR solution (if it exists) is not unique and can be chosen to minimize the noise power at the receiver. These findings are demonstrated by examples where we compare the performance of fractionally spaced zero forcing equalizers to that of the corresponding minimum mean-squared error solution.

The design of time-domain equalizers or TEQs for discrete multitone modulation (DMT) systems has recently received much attention. In this paper, we present a generalization of one such design method which takes into account the noise observed in a DMT channel. Furthermore, we show how this generalization can be used for the design of fractionally spaced equalizers or FSEs. Experimental results are presented showing that our design method performs better than other known techniques.

The cyclic prefix is commonly used in the context of frequency domain equalization in DMT channels. We observe that it can be used in more general contexts and show its advantages in blind equalization, especially for non-minimum phase channels.

Cyclic prefix based equalizers are widely used for high-speed data transmission over frequency selective channels. Their use in conjunction with DFT filterbanks is especially attractive, given the low complexity of implementation. Some examples include the DFT-based DMT systems. We consider a general cyclic prefix based system for communication and show that the equalization performance can be improved by simple pre- and post-processing aimed at reducing the noise at the receiver. This processing is done independently of the ISI cancellation performed by the frequency domain equalizer.

A new contribution to generalized sampling of bandlimited signals based on the so-called chromatic derivative operators was recently introduced by Ignjatovic (see Kromos Technology, Los Altos, CA. [Online] Tech. Rep. 1, 2001). Chromatic derivatives are linear combinations of the ordinary derivatives, where the coefficients of the combination are derived from orthogonal polynomial theory. This article describes the connection between these operators and the well-established ideas of perfect reconstruction and biorthogonality in analog filter banks.

Recently, the authors proposed a Look Up Table (LUT) based method for inverse halftoning of images. The LUT for inverse halftoning is obtained from the histogram gathered from a few sample halftone images and corresponding original images. Many of the entries in the LUT are unused because the corresponding binary patterns hardly occur in commonly encountered halftones. These are called nonexistent patterns. In this paper, we propose a tree structure which will reduce the storage requirements of an LUT by avoiding nonexistent patterns. We will demonstrate the performance on error diffused images and ordered dither images. Then, we introduce LUT based halftoning and tree-structured LUT (TLUT) halftoning. Even though TLUT method is more complex than LUT halftoning, it produces better halftones and requires much less storage than LUT halftoning.We will demonstrate how error diffusion characteristics can be achieved with this method. Afterwards, our algorithm will bet rained on halftones obtained by Direct Binary Search (DBS).The complexity of TLUT halftoning is higher than error diffusion algorithm but much lower than DBS algorithm. Also, the halftone quality of TLUT halftoning increases if the size of TLUT gets bigger. Thus, halftone image quality between error diffusion and DBS will be achieved depending on the size of tree-structure in TLUT algorithm.

Suppose we wish to analyze a noisy signal using a filter bank (FB) and apply noise suppression schemes such as Wiener filters in the subbands of the FB. This paper formalizes and studies the problem of finding the best FB for this purpose. The best FB depends on the class of allowed FB, the type of subband processing, and the statistics of the input signal and additive noise. Recently we have shown the optimality of the so-called principal component filter bank (PCFB) for several signal processing problems. In particular the PCFB is the optimum orthonormal FB for many schemes for suppression of white noise. With colored noise however the optimization is considerably more involved, and PCFB optimality is much more restricted. We present several results on the colored noise suppression problem. We develop an algorithm to find the exact globally optimum unconstrained orthonormal FB for piecewise constant input signal and noise spectra. This thus allows approximation of the optimum FB for any spectra to any desired accuracy. We examine the role of PCFB in the optimization.

We propose a method to modify the histogram of a signal to a desired specific histogram. Traditionally, points having the same value in the input signal are all mapped to same value in the output signal. Hence, the desired histogram can only be approximated. Here we formulate our problem as finding a transformation such that the error between the input and output signal is minimized and the output signal has the desired histogram. It turns out that this problem is equivalent to an integer linear programming problem. This method might be specifically useful for histogram-based watermarking and compression.

One problem of great interest to the signal processing community is that of estimating the frequencies of sinusoids buried in noise. Traditional methods applied to a fullband signal fail to estimate accurately when the signal-to-noise ratio (SNR) or spacing between frequencies is small. They also fail when the noise is not white and its statistics are unknown. We consider these methods when applied to the subbands of a filter bank and show that, through proper choice of analysis filters, the local SNR and frequency spacing increase by the decimation ratio. We also show that the subband noise processes are, on average, more "white" than the fullband one in terms of the spectral flatness measure. This suggests that if the noise statistics are unknown, there will be less error by estimating in the subbands as opposed to the fullband. Experimental results support this theory, as we show.

It is well-known that certain non-bandlimited signals such as splines can be reconstructed from uniformly spaced samples similar to bandlimited signals. This usually requires noncausal IIR filters. We revisit this result and consider extensions such as derivative sampling theorems and pulse sampling theorems. It turns out that spline-like signals can often be reconstructed from joint sampling of amplitude and derivative using only FIR filters. We also briefly consider discrete time versions of these results.

The concept of multiple input multiple output (MIMO) biorthogonal partners arises in many different contexts, one of them being multiwavelet theory. They also play a central role in the theory of MIMO channel equalization, especially with fractionally spaced equalizers. We explore some further theoretical properties of MIMO biorthogonal partners. These include the conditions for the existence of MIMO biorthogonal partners and their application in finding the solution for the least squares signal approximation problem.

It has previously been claimed that a class of filter banks called the principal component filter banks (PCFB) is optimal for digital communication using discrete multitone modulation. In this paper we revisit this result and examine the origin of this optimality. We provide illustrative examples comparing the PCFB with traditional filters. We also provide a rigorous proof of the claim that the bit rate is maximized by the PCFB.

Channel equalization is an important step in most applications of digital communications. In this paper we consider the equalization of multiple input multiple output (MIMO) channels. To that end we derive the theory of MIMO biorthogonal partners, a concept that has already been introduced (only in the scalar case) by the authors. We develop conditions for the existence of an FIR MIMO biorthogonal partners and describe their application in the MIMO channel equalization. We also show that it is possible to exploit the non-uniqueness of FIR MIMO biorthogonal partners in order to design flexible fractionally spaced MIMO equalizers that will be more robust to the channel noise.

In this paper we propose look-up table (LUT) based methods for inverse halftoning of images. The LUT for inverse halftoning is obtained from the histogram gathered from a few sample halftone images and corresponding original images. The method is extremely fast (no filtering is required) and the PSNR and visual image quality achieved is comparable to the best methods known for inverse halftoning. The LUT inverse halftoning method does not depend on the specific properties of the halftoning method, and can be applied to any halftoning method. Then, an algorithm for template selection for LUT inverse halftoning is introduced. We demonstrate the performance of the LUT inverse halftoning algorithm on error diffused images and ordered dithered images. We also extend LUT inverse halftoning to color halftones.

B-splines are commonly used for continuous representation of discrete time signals. This kind of representation proves to be very useful in applications such as image interpolation, rotation and edge detection. In all these applications, the first step is to compute the B-spline coefficients of the signal, and this involves the use of an IIR noncausal filter called the direct B-spline filter. The signal reconstruction is achieved using the indirect B-spline filter, which in many applications operates at a higher rate. In this paper, we introduce a simplified implementation of the signal reconstruction part that will significantly reduce the overall complexity. We also show that the direct B-spline filter can safely be replaced with a short FIR filter, without compromising the performance of the traditional method. Numerous examples show both visually and numerically that the differences between this method and the traditional one are indeed very small. Finally, we report the performance of these newly proposed methods in other image processing applications such as edge detection and least squares approximation.

We have made explicit the precise connection between the optimization of orthonormal filter banks (FBs) and the principal component property: the principal component filter bank (PCFB) is optimal whenever the minimization objective is a concave function of the subband variances of the FB. This explains PCFB optimality for compression, progressive transmission, and various hitherto unnoticed white-noise, suppression applications such as subband Wiener filtering. The present work examines the nature of the FB optimization problems for such schemes when PCFBs do not exist. Using the geometry of the optimization search spaces, we explain exactly why these problems are usually analytically intractable. We show the relation between compaction filter design (i.e., variance maximization) and optimum FBs. A sequential maximization of subband variances produces a PCFB if one exists, but is otherwise suboptimal for several concave objectives. We then study PCFB optimality for colored noise suppression. Unlike the case when the noise is white, here the minimization objective is a function of both the signal and the noise subband variances. We show that for the transform coder class, if a common signal and noise PCFB (KLT) exists, it is, optimal for a large class of concave objectives. Common PCFBs for general FB classes have a considerably more restricted optimality, as we show using the class of unconstrained orthonormal FBs. For this class, we also show how to find an optimum FB when the signal and noise spectra are both piecewise constant with all discontinuities at rational multiples of /spl pi/.

The discrete multitone modulation (DMT) systems have been widely used in various applications. The DMT system can be considered as a dual of a subband coder, obtained by using the synthesis bank as the transmitter and analysis bank as the receiver. In designing optimal subband coders, the objective is to minimize output quantization noise, whereas in the problem of designing optimal DMT system, the objective function to be minimized is the transmitted power. We show that the design of optimal DMT systems can be formulated as a hypothetical design problem of optimal subband coders. The solution of optimal DMT system can be obtained using existing design methods for optimal biorthogonal subband coders.

In a previous paper we have proposed a method for inverse halftoning of monochrome images. It is a look up table (LUT) based method, obtained from the histogram gathered from a few sample halftone images and corresponding original images. The method is extremely fast (no filtering is required) and the image quality achieved is comparable to the best methods known for inverse halftoning. The method does not depend on the specific properties of halftoning method, and can be applied to any halftoning method. In this paper, we discuss how to choose the template recursively for the LUT. Afterwards, we propose an LUT based inverse halftoning method for color halftones. Color inverse halftoning can be done independently for each color plane or the correlation between the planes can be exploited. We also show how to choose the template for color inverse halftoning.

We have previously applied the look up table (LUT) method for inverse halftoning. We also proposed a tree-structure LUT inverse halftoning in order to reduce the memory requirements of the LUT method. We introduce the LUT based halftoning method. Pixels from a causal neighborhood and the contone value of the current pixel are included in the LUT. The LUT halftoning requires no arithmetic operations other than memory access. For any halftoning method, a sample set of images and halftones of these images is used. We introduce the tree-structure LUT (TLUT) halftoning. Even though this method is more complex than LUT halftoning it produces better halftones and it requires much less storage than LUT halftoning. We demonstrate how the error diffusion characteristics can be achieved with this method. The algorithm is trained on halftones obtained by direct binary search (DBS) images. The complexity of the tree-structure LUT halftoning is higher than the error diffusion algorithm but much lower than the DBS algorithm. Also, the halftone quality of TLUT halftoning increases if the size of TLUT gets larger. Thus, the halftone image quality between the error diffusion and DBS is achieved depending on the size of the tree-structure in the TLUT algorithm.

Principal component filter banks (PCFBs) sequentially compress most of the input signal energy into the first few subbands, and are mathematically defined using the notion of majorization. In a series of recent works, we have exploited connections between majorization and convexity theory to provide a unified explanation of PCFB optimality for numerous signal processing problems, involving compression, noise suppression and progressive transmission, However PCFBs are known to exist for all input spectra only for three special classes of orthonormal filter banks (FBs): any class of two channel FBs, the transform coder class and the unconstrained class. This paper uses the developed theory to describe techniques to examine existence of PCFBs. We prove that the classes of DFT and cosine-modulated FBs do not have PCFBs for large families of input spectra. This result is new and quite different from most known facts on nonexistence of PCFBs, which usually involve very specific examples and proofs with numerical optimizations.

In this paper we propose a novel method for inverse halftoning of images. The method is basically a Look Up Table (LUT) based method. The LUT for inverse halftoning is obtained from the histogram gathered from a few sample halftone images and corresponding original images. The method is extremely fast (no filtering is required) and also the image quality achieved is comparable to the best methods known for inverse halftoning. The method does not depend on the specific properties of halftoning method, and can be applied to any halftoning method.

Discrete multitone modulation is an attractive method for communication over a nonflat channel with possibly colored noise. The uniform DFT filter bank and cosine modulated filter bank have in the past been used in this system because of low complexity. We show in this paper that principal component filter banks, which are known to be optimal for data compression and denoising applications, are also optimal for a number of criteria in DMT communication.

Unlike the error diffusion method, the dot diffusion method for digital halftoning has the advantage of pixel-level parallelism. However, the image quality offered by error diffusion is still regarded as superior to most of the other known methods. We show how the dot diffusion method can be improved by optimization of the so-called class matrix. By taking the human visual characteristics into account we show that such optimization consistently results in images comparable to error diffusion, without sacrificing the pixel-level parallelism. Adaptive dot diffusion is also introduced and then a mathematical description of dot diffusion is derived. Furthermore, inverse halftoning of dot diffused images is discussed and two methods are proposed. The first one uses projection onto convex sets (POCS) and the second one uses wavelets. Of these methods, the wavelet method does not make use of the knowledge of the class matrix. Embedded multiresolution dot diffusion is also discussed, which is useful for rendering at different resolutions and transmitting images progressively.

Nonuniform filter-banks (FBs) have traditionally been built either by cascading uniform ones in a tree structure or by direct design methods that lead to near-perfect reconstruction. However many theoretical issues remain unresolved. This paper begins by pointing out a number of these issues, and summarizes the known conditions for existence of nonuniform perfect reconstruction (PR) FBs. As a new contribution, we simplify some of these conditions and make them more explicit. We provide examples that illustrate some hitherto unobserved connections between these conditions.

The dot diffusion method for digital halftoning has the advantage of parallelism unlike the error diffusion method. The method was previously improved by optimization of the so-called class matrix so that the resulting halftones are comparable to the error diffused halftones. We give a mathematical description of the dot diffusion method. This description is then applied in inverse halftoning.

It is well known that linear time-invariant (LTI) systems produce exponential outputs in response to exponential inputs. The purpose of this paper is to draw attention to the fact that the same result holds for the broader class of homogeneous time-invariant (HTI) systems, though the concept of a frequency response is of little use for such systems.

In this paper we have two interesting results. One is of theoretical interest and the other practical. The theoretical result is that the optimum FIR orthonormal filter bank of a fixed finite degree that maximizes the coding gain does not always contain an optimum compaction filter. In other words, in general, there does not exist a principal component filter bank (PCFB) of a given nonzero degree. This is sharply in contrast to the cases of transform coders and ideal subband coders where the existence of PCFB's are assured by their very construction. The practical result of the paper is that constraining the filter corresponding to the largest subband variance to be a compaction filter does not result in a significant loss of performance for practical input signals. Since there exist very efficient methods to design FIR compaction filters and since the best completion of the filter bank given the first filter is trivially done by a KLT, we see that this is an extremely efficient method despite the fact that it is suboptimum.

We introduce a new approach to adapt a 2-channel FIR orthonormal filter bank to the input second order statistics. The problem is equivalent to optimizing the magnitude squared response F(e/sup jw/)=|H(e/sup jw/)|/sup 2/ of one of the subband filters for maximum energy compaction under the constraint that F(e/sup jw/) is Nyquist(2). The novel algorithm enjoys important advantages that are not present in previous work. First, we can ensure the positivity of F(e/sup jw/) over all frequencies simultaneously with the Nyquist constraint. Second, for a fixed input power spectrum, the resulting filter F/sub opt/(z) is guaranteed to be a global optimum due to the convexity of the new formulation. The optimization problem is expressed as a multi-objective semi-definite programming problem which can be solved efficiently and with great accuracy using interior point methods. Third, the new algorithm is extremely general in the sense that it works for any arbitrary filter order N and any given input power spectrum. Finally, obtaining H/sub opt/(e/sup jw/) from F/sub opt/(e/sup jw/) does not require an additional spectral factorization step.

Cyclic signal processing refers to situations where all the time indices are interpreted modulo some integer L. Since the frequency domain is a uniform discrete grid, there is more freedom in theoretical and design aspects. The basics of cyclic (L) multirate systems and filter banks have already appeared in the literature, and important differences between the cyclic and noncyclic cases are known. Since there is a strong connection between paraunitary filter banks and orthonormal wavelets, some deeper questions pertaining to cyclic (L) paraunitary matrices are addressed in this paper. It is shown that cyclic (L) paraunitary matrices do not in general have noncyclic paraunitary FIR interpolants, though IIR interpolants can always be constructed. It is shown, as a consequence, that cyclic paraunitary systems cannot in general be factored into degree one nonrecursive paraunitary building blocks. The connection to unitariness of the cyclic state space realization is also addressed.

The dot diffusion method for digital halftoning has the advantage of parallelism unlike the error diffusion method. However, the image quality offered by error diffusion is still regarded as superior to other known methods. In a previous paper we showed how the dot diffusion method can be improved by optimization of the so-called class matrix. In this paper we first review the dot diffusion algorithm and the optimization of the class matrix. A method for inverse halftoning of dot diffused images is then proposed. The method uses wavelet decomposition to eliminate the halftoning noise and does not make use of the knowledge of the class matrix.

The traditional designs for the prototype filters of cosine modulated filterbanks usually involve nonlinear optimizations. We propose limiting the search of the prototype filters to the class of filters obtained using Kaiser windows. The design process is reduced to the optimization of a single parameter. An example is given to show that very good designs can be obtained in spite of the limit of search.

Energy compaction has proven to be an essential concept in signal-adapted data compression. In particular, optimization of orthonormal subband coders for a given power spectrum directly leads to optimal energy compaction filters. We consider some new design methods and properties of optimal FIR energy compaction filters. In particular, we propose a very efficient method called the window method for the general M-channel case. The method does not involve any sophisticated optimization tools and terminates in a finite number of elementary steps. Compaction gains achieved by the method are very close to the optimal ones. As the filter order increases the filters of the proposed method converge to the optimum ideal compaction filters.

In this paper, we statistically optimize a well known class of IIR two channel orthonormal filter banks parameterized by a single coefficient when subband quantizers are present. The optimization procedure is extremely simple and very fast compared for example to the linear programming method used in the FIR case to achieve similar compaction (coding) gains. The special form of the filters assure the existence of a zero at /spl pi/ which can be important for some wavelet applications and eliminate some of the major concerns that arise in the FIR design case. Finally, the compaction gain obtained is high and numerically very close to two (ideal case) for low pass spectra, high pass spectra and certain cases of multiband spectra. For these cases, the use of higher order IIR filters does not increase the compaction (coding) gain.

We introduce the fundamentals of cyclic multirate systems and filter banks and present a number of important differences between the cyclic and noncyclic (traditional) cases. Some of the additional freedom offered by cyclic systems is pointed out, and a number of open issues are summarized.

We provide a simple proof of the minimum phase property of the optimum linear prediction polynomial. The proof follows directly from the fact that the minimized prediction error has to satisfy the orthogonality principle. Additional insights provided by this proof are also discussed.

It is well-known that continuous time bandlimited signals can be sampled without creating aliasing if the sampling period is small enough. It is also known that if x(t) is a bandpass signal, the passbands of X(/spl Omega/) must be located properly for alias-free maximal sampling. Similar situations arise in discrete time case. This paper addresses these issues for two-dimensional (2D) one- and two-parallelogram signals, which are respectively the classes of 2D signals (continuous or discrete time) whose Fourier transforms have supports consisting of one and two parallelograms. In this paper, we derive necessary and sufficient conditions such that a one- or two-parallelogram signal (continuous and discrete time) allows maximal alias-free sampling.

We introduce a polyphase representation for linear time-varying (LTV) filters. Using the proposed polyphase approach, we are able to show some unusual properties of LTV filter bank (FB) that have not been pointed out before. The problem of interchangeability of analysis and synthesis banks is considered. Lossless TVFBs is studied in detail. Perfect reconstruction (PR) can always be obtained for lossless TVFBs. However, in general a PR lossless TVFB will only generate a tight frame.

In a previous paper we derived a set of necessary and sufficient conditions for maximizing the coding gain in an orthonormal filter bank. These are referred to as the decorrelation and majorization conditions. While each of these two conditions is individually only necessary and not sufficient, they together form a set of necessary and sufficient conditions. In this paper we show how to relate these to the idea of energy compaction. This relation is then used to identify the optimum analysis filters one at a time.

The existing sampling theory for MRA subspaces is generalized to several more cases. We consider derivative sampling, multiband sampling and sampling of wide sense stationary (WSS) random processes. We also show that the synthesizing functions form a Riesz basis for the corresponding MRA subspace The case of wavelet subspaces is also considered.

If a discrete time signal x(n) is bandlimited appropriately we can decimate it without aliasing. However, there exists a broad class of non bandlimited signals which can be recovered perfectly from their decimated versions. We consider both uniform and nonuniform decimation of this kind and explore some applications, especially in noise shaping and in /spl Sigma/-/spl Delta/ modulator type of architectures.

In this paper, we construct two-dimensional (2D) FIR paraunitary Cosine Modulated Filter Banks (CMFB). All the analysis and synthesis filters are cosine-modulated versions of a 2D non-separable prototype; each filter consists of two shifts of the prototype. The design of the filter bank involves only the optimization of the prototype. Furthermore, the complexity of the 2D filter bank is that of the prototype plus two non-separable DCT matrices.

In this paper, we consider the problem of computation of wavelet functions generated from perfect reconstruction filter banks with rational filters. We derive the dilation equations in recursive form and show how to exploit the recursive equations to compute the limit functions. We also derive a recursive equation for the cascade algorithm introduced by Daubechies. The recursive equations link the limit functions directly to the coefficients of the difference equation instead of impulse responses. In both cases, the proposed recursive method has significant computational saving. Furthermore, all the low sensitivity and efficient structures (such as lattice structure) developed in signal processing can be directly applied for wavelet computation. As an application, we show that the class of IIR orthogonal cardinal scaling functions can be computed exactly at all dyadic rationals by using the recursive equations. Recursive formulas for the 2D quincunx wavelets are also derived.

Anticausal inversion of IIR transfer functions has gained importance in recent years, in the efficient implementation of IIR digital filter banks. In this paper we first introduce the idea of a causal dual, as an intermediate step in the implementation of anticausal IIR inverses. With time reversal operators at the input and output of the causal dual, we get the anticausal inverse of the original structure. The causal dual eliminates the need for similarity transformations, during a key step called blockwise state transfer, in implementing anticausal inverses. In the paper we identify efficient structures for causal duals of standard structures like the direct-form, cascade-form, coupled form, and IIR lattice structures, including the tapped lattice.

If a discrete time signal x(n) is obtained as the output of an interpolation filter F(z), it is natural to expect that it can be recovered from the decimated samples x(Mn), even though the signal is not bandlimited except in the ideal case. However, unless F(z) is a Nyquist filter, stability of reconstruction is not guaranteed. There are cases where x(n) cannot be recovered from the uniformly spaced samples x(Mn) in a stable manner, for example, when all the polyphase components of F(z) have unit-circle zeros. We provide precise theorems which show that even under such situations, stable reconstruction from a nonuniformly decimated version is often possible.

Analysis/synthesis filter banks with perfect reconstruction property have attracted much attention. In some applications, particularly image coding, it is desirable to design filter banks in which the filters have linear phase. We present a method of linearizing the passband phase response of filters in any given filter bank. While linearizing the phase response, this method preserves the magnitude response of the filters, the perfect reconstruction property, and the paraunitary property (orthonormality). We present the eigen-approach design and the anticausal implementation of this technique. Using this technique, we illustrate the importance of linear phase in subband coding.>

Causal FIR matrices with anticausal FIR inverses have a key role in the theory of FIR perfect reconstruction filter banks. The author explores the theory of such matrices. Some general results on nature of inverses of first order causal FIR matrices are then presented. This leads, in particular, to a complete parameterization of the biorthonormal lapped transform (BOLT) reported in Vaidyanathan [1993].>

In this paper a new type of maximally decimated FIR cosine modulated filter bank is proposed. Each analysis and synthesis filter in this filter bank has linear phase. We can design the system to have approximate reconstruction property (pseudo-QMF system) or perfect reconstruction property (PR system). The filter bank is paraunitary in the PR case. Although there are 2M channels in the new system, the cost (in terms of design and implementation complexity) is comparable to that of an M channel system. Correspondingly, the coding gain of the new system is also comparable to that of a traditional M channel system (rather than a 2M channel system). Examples will be given to demonstrate that very good attenuation characteristics can be obtained with the new system.>

A new class of two-channel biorthogonal filter banks is derived. The framework covers two useful subclasses: (i) causal stable IIR filter banks; (ii) linear phase FIR filter banks. Perfect reconstruction is structurally preserved and the structural complexity is very low. Filter banks of high frequency selectivity can be achieved by simply designing a single transfer function. Furthermore zeros of arbitrary multiplicity at aliasing frequency can be easily imposed, for the purpose of generating wavelets with regularity property. We also map the proposed 1D framework into 2D. The mapping preserves: (i) perfect reconstruction; (ii) stability in the IIR case; (iii) linear phase in the FIR case; (iv) zeros at aliasing frequency and (v) frequency characteristic of the filters.>

Biorthonormal filter banks are essentially maximally decimated perfect reconstruction filter banks. The role of causal transfer matrices with anticausal inverses in biorthonormal filter bank theory has recently been recognized. These matrices help to characterize all biorthonormal filter banks in the FIR case; in the IIR case they are useful in finding stable anticausal inverses of analysis banks (when stable causal inverses do not exist), thereby enabling stable reconstruction of signals from subbands. This paper is dedicated to a discussion of the properties of transfer matrices with anticausal inverses.>

The Chinese remainder theorem (CRT) [McClellan and Rader 1979] has been well known for applications in fast DFT computations and computer arithmetic. Guessoum and Mersereau [1986] first made headway in extending the CRT to multidimensional (MD) nonseparable systems and showing its usefulness. The present letter generalize the result and present a more general form. This more general MDCRT is an exact counterpart of 1DCRT.>

The authors review the fundamentals of multidimensional (M-D) multirate signal processing and present recent and new developments in M-D multirate systems. A method is presented for deriving all parallelepiped-shaped filters in M-D multirate applications from an appropriate 1-D filter. It is shown that the generalized-pseudocirculant property is necessary and sufficient for an M-D maximally decimated filter-bank system to be free from aliasing. It is shown how the Smith form, Smith-McMillan form, and the least common multiples of integer matrices can resolve many nonseparable M-D multirate problems. The condition for alias-free decimation and the multistage design of decimation systems are mentioned.>

Multidimensional (MD) multirate systems, which find applications in the coding and compression of image and video data, have attracted much attention. The basic building blocks in a MD multirate system are the decimation matrix M, the expansion matrix L, and MD digital filters. With D denoting the number of dimensions, M and L are D*D nonsingular integer matrices. When these matrices are diagonal, most of the one-dimensional multirate results can be extended automatically. However, for the nondiagonal case, these extensions are nontrivial. One example of this nature is the commutativity of MD decimation and expansion matrices. Using the concepts of coprimeness and least common right/left multiples of integer matrices, a set of necessary and sufficient conditions is derived for a decimation matrix and an expansion matrix to commute. This commutativity is also used to derive an efficient polyphase implementation of an MD decimation system with rational decimation matrix.>

Binary tree-structured filter banks have been employed in the past to generate wavelet bases. The equivalence between binary paraunitary tree-structures and orthonormal wavelet bases is proven. It is known that a binary tree with paraunitary filters on each level generates a discrete time orthonormal wavelet basis. It is shown that every discrete-time orthonormal wavelet basis can be generated using paraunitary binary trees. Next, this analysis is extended to arbitrary tree structures such as those used for generating wavelet packets. It is shown that an arbitrary tree with paraunitary filers gives an orthonormal basis of wavelet packets. The strict converse is not true, but a weaker result is presented.>

The authors present a derivation of the necessary and sufficient condition on the polyphase components of a linear-phase prototype (length N=2 mM) such that the polyphase component matrix of the filter bank is lossless. This in turn ensures that the modulated filter bank satisfies the PR (perfect reconstruction) property. An efficient design procedure (which involves fewer parameters to be optimized than other approaches) is presented. By this approach, FIR (finite-impulse-response) PR filter banks can be designed for an arbitrary number of channels. Moreover, since both the analysis and synthesis filter banks are obtained by modulation, they can be implemented very efficiently (using the discrete cosine transform). The design procedure is outlined and a design example is presented.>

The authors study the statistical properties of the outputs of some basic multirate filtering operations when the input is a wide-sense-stationary (WSS) or a cyclo-WSS (CWSS) process. They give necessary and sufficient conditions under which the output remains WSS or CWSS. For some multirate filters, the output response to a WS input is CWSS. Expressions for the periods of cyclostationarity for such cases are given. As an application of the theory, the optimal (Wiener) solution for a new efficient multirate adaptive filtering method suitable for identification of bandlimited channels is derived. It is shown that the optimal (Wiener) filter is a linear periodically time-varying (LPTV) filter. Simulations are included which verify that an LPTV adaptive filtering structure gives better performance than a transversal adaptive filtering structure.>

Multirate topics such as decimation, interpolation, polyphase decomposition, and filter bank theory have been extended in the past for the case of multidimensional systems. It is pointed out that the decimation matrix plays a crucial role in these extensions. Unless the matrix is diagonal, separable techniques cannot be used either for theoretical derivations or practical implementations. In this context, the author introduces a diagonalization technique for the decimation matrix, which brings the results closer to the separable (hence one-dimensional) case.>

The basic concepts and building blocks in multirate digital signal processing (DSP), including the digital polyphase representation, are reviewed. Recent progress, as reported by several authors in this area, is discussed. Several applications are described, including subband coding of waveforms, voice privacy systems, integral and fractional sampling rate conversion (such as in digital audio), digital crossover networks, and multirate coding of narrowband filter coefficients. The M-band quadrature mirror filter (QMF) bank is discussed in considerable detail, including an analysis of various errors and imperfections. Recent techniques for perfect signal reconstruction in such systems are reviewed. The connection between QMF banks and other related topics, such as block digital filtering and periodically time-varying systems, is examined in a pseudo-circulant-matrix framework. Unconventional applications of the polyphase concept are discussed.>

The authors present a perfect-reconstruction FIR (finite impulse response) linear-phase lattice structure for the three-channel QMF (quadrature mirror filter) bank. Both the analysis and the synthesis filters are linear-phase. To speed up the design time, the pairwise mirror-image condition is imposed on the resulting lattice structure. A design example is presented, and the complexity of the analysis bank is discussed.>

Based on the multistage approach, a design procedure is presented for finding a spectral factor of an mth-band filter and for designing multistage decimation filters. The proposed design method finds spectral factors of mth-band FIR (finite-impulse response) filters without direct computation, and yields filters with much higher attenuation than would be possible by conventional methods. Such mth-band filters are used in filter-bank designs, including perfect-reconstruction systems.>

A property of FIR (finite-impulse response) lossless systems is introduced, leading to substantial improvement in the sign procedure for perfect-reconstruction QMF (quadrature mirror filter) banks. The property enables the designer to initialize the coefficients of a lattice structure (which characterizes the analysis bank), in such a way as to speed up to the convergence. A design example is provided. Compared to other methods, the proposed method is shown to converge faster, and always leads to much improved attenuation characteristics for a given filter length.>

The properties of digital all-pass filters are reviewed and a broad overview of the diversity of applications in digital filtering is provided. Starting with the definition and basic properties of a scalar all-pass function, a variety of structures satisfying the all-pass property are assembled, with emphasis placed on the concept of structural losslessness. Applications are then outlined in notch filtering, complementary filtering and filter banks, multirate filtering, spectrum and group-delay equalization, and Hilbert transformations. In all cases, the structural losslessness property induces very robust performance in the face of multiplier coefficient quantization. Finally, the state-space manifestations of the all-pass property are explored, and it is shown that many all-pass filter structures are devoid of limit cycle behavior and feature very low roundoff noise gain.>

In this paper, a scheme for perfect reconstruction in M channel, maximally decimated QMF banks is first presented, for arbitrary M. The solutions are such that the analysis and synthesis filters are FIR and of the same length. Based on the theory, lattice structures for the two-channel case are derived, which offer an efficient design as well as implementation procedure for two-channel perfect reconstruction systems. Such lattice implementations are robust in the sense that the perfect-reconstruction property is preserved in spite of coefficient quantization.

The prediction of samples of a band-limited real signal xa(t) from a finite number of past samples is considered. It is shown how a signal-independent linear predictor of finite order can be constructed based on Chebyshev polynomials, such that the prediction error tends to zero for sampling rate exceeding the Nyquist rate.

A number of well-known stability-test procedures for continuous-and discrete-time systems are re-examined in a unified manner, leading to well-defined network-theoretic interpretations. The representation and network interpretation are based on the fact that the stability of any linear system (scalar or multivariable) is equivalent to the stability of a related all-pass system, which in turn can always be synthesized as a cascade of (scalar or matrix) two-pair all-pass (lossless) networks. The original system of interest is stable if and only if each all-pass two-pair is stable (and hence "lossless bounded real"). As a result of this interpretation, a number of related issues, such as enumeration of unstable poles, prematured terminations, and singularity situations can all be approached in a unified manner, based only on "two-pair extraction formulas." In addition, the network interpretation also leads to direct test procedures for testing relative stability, and the stability of multi-input, multi-output systems.

A general framework is developed for uniform DFT, parallel quadrature mirror filter banks, which enables us to derive a number of conclusions in an elegant manner. Closed form expressions for the synthesis filters are obtained both for FIR and IIR case, and a number of properties of importance are placed in evidence.

It is shown that any arbitrary FIR transfer function can be implemented in the form of a passive structure, resulting in low coefficient sensitivity. The building blocks are planar-rotation operators, and internal signal nodes are automatically L2-scaled. Denormalized versions of the building blocks are also shown. Design examples are included.

It is shown that a wide class of real-coefficient, doubly-complementary IIR transfer-function pairs can be implemented by means of a single complex allpass filter. For a real input sequence, the real part of the output sequence of the complex allpass filter corresponds to one of the transfer functions G(z) (for example, low-pass), whereas the imaginary part of the output sequence corresponds to its "complementary" filter H(z) (for example, highpass). Since the resulting implementation is structurally lossless, G(z) and H(z) have very low passband-sensitivity. Numerical design examples are included to demonstrate the ideas.

The class of digital filter pairs satisfying two types of complementary properties simultaneously is reexamined. The pair is required to have complementary square magnitude characteristics with respect to a constant and transfer functions complementary with respect to an allpass function. This filter class, called doubly complementary filters is then extended to have M filters with complex outputs. Basic properties of the filters are discussed. It is shown that all the filters in the bank can be implemented as linear combinations of the same low order allpass filters. The individual filters can have different bandwidths and tolerances. The filter bank can also produce [M/2]+1 real outputs with allpass complementary responses that can be arbitrarily added up to form a variety of allpass complementary filters. The filters have low coefficient sensitivities in their passbands if the allpass sections are implemented with structures that are canonic with respect to the coefficients.

A technique is presented for designing linear-phase digital FIR filters, with a prescribed degree of flatness in the passband, and a prescribed (equiripple) attenuation in the stopband. The design is based entirely on appropriate use of the McClellan-Parks algorithm along with certain maximally flat building blocks.

A new type of cascade form structure for digital filtering is proposed, with each building block being a second order section, that satisfies certain passivity properties. This passivity is essentially a "structure-induced" boundedness on the transfer function magnitude, and leads to low passband sensitivity. In addition, the cascade nature ensures low stopband sensitivity, as zeros on the unit circle continue to remain on the unit circle in spite of the quantization. The structure itself is independent of the pole locations and therefore meets a wide range of filtering applications.

In a recent paper [1], it is shown that a fundamental requirement for low passband sensitivity realization of a digital transfer function is that the implementation be structurally passive, or bounded. In this paper, a general procedure for developing low-sensitivity realizations of a transfer function is advanced. The resulting structures are in the form of a cascade connection of basic digital two-pair structures satisfying a "lossless" property in the z-domain. The methods advanced here cover the well-known wave digital filters and the Gray-Markel lattices as special cases. The synthesis procedure is entirely z-domain based, and does not make reference to continuous time networks, unlike the wave digital filters which are designed starting from a continuous time network.