Search

While frequency-domain algorithms have been demonstrated to be powerful for conventional nonlinear signal processing, there is still not much progress in literature dedicated to nonlinear graph signal processing in frequency domain. The difficulties come from the irregular structure of graph signals and the lack of a straightforward description for the nonlinear relationship between input and output graph signals. In this paper, a distributed nonlinear polynomial graph filter (NPGF) is proposed to characterize the nonlinear input-output relationship by employing polynomial-type nonlinearity based on Hadamard product. Then, the nonlinear output graph signal is reformulated based on the multi-dimensional inverse graph Fourier transform (GFT), where the m -dimensional GFT coefficients are defined as explicit functions of input graph spectrum and filter structural factors (filter parameters, graph shift matrix, nonlinear degree, and graph shift order). The effects of filter structural factors on the output graph spectrum are further evaluated by proposing graph frequency response (GFR) coefficients, which inherently characterize the irregular structural behaviors of a distributed NPGF in frequency domain. The nonlinear output graph spectrum is then developed based on GFR vectors by mapping the GFR coefficients in the tensor formulation to the output GFT coefficients in the vector expression. This can greatly improve the efficiency in calculating the output graph signal if the input signal only involves a few frequency components. Finally, algorithms are proposed to design the filter parameters for the desired output signal. Numerical studies are presented to illustrate and validate the proposed frequency-domain framework for nonlinear graph signal processing.

In this paper, we propose a generalized singular value decomposition (GSVD) for polynomial matrices, or polynomial GSVD (PGSVD). We then consider PGSVD-based beamforming for two-user, frequency-selective, multiple-input multiple-output (MIMO) multicasting. The PGSVD can jointly factorize two frequency-selective MIMO channels, producing a set of virtual channels (VCs), split into: private channels (PCs) and common channels (CCs). An important advantage of the proposed PGSVD-based beamformer, over the application of GSVD independently to each frequency bin of the orthogonal frequency division multiplexing (OFDM) scheme, is that it can facilitate different modulation and/or access schemes to various users. Using computer simulations, we characterize the bit error rate performance of our two-user MIMO multicasting system for different PCs/CCs configurations. Here, we also propose an OFDM-GSVD benchmark system, and show that our PGSVD-based beamformer compares favorably to this benchmark under erroneous and uncertain MIMO channel conditions, in addition to its advantage of facilitating heterogeneous modulation and access for various users.

Graph signal processing (GSP) is a field that deals with data residing on irregular domains, i.e. graph signals. In this field, the graph filter bank is one of the most important developments, owing to its ability to provide multiresolution analysis of graph signals. However, most of the current research on graph filter bank focuses on static graph signals. The research does not exploit the temporal correlations of time-varying signals in real-world applications, such as in wireless sensor networks. In this paper, the theory and design of joint time-vertex nonsubsampled filter bank are developed, using a generalized product graph framework. Several methods are proposed to design the filter bank with perfect reconstruction, while still achieving filters with good spectral characteristics. A notable feature of the designed filter bank is that it can be completely realized in a distributed manner. The subband filters are either of polynomial type or defined implicitly via iterative equations. In either case, implementing the subband filters requires only the exchange of information between neighboring nodes. The filter banks are therefore of low implementation complexity and suitable for processing large time-varying datasets. Numerical examples will demonstrate the effectiveness of the proposed designed methods. Application in time-varying graph signal denoising will show the superiority of joint time-vertex filter bank over other methods.

This paper proves that every non-trivial, linear time-invariant (LTI) system of the first order shows a complexity blowup if it is simulated on a digital computer. This means that there exists a low-complexity input signal, which can be generated on a Turing machine in polynomial time, but such that the output signal of the LTI system has high complexity in the sense that the computation time for determining an approximation up to $n$ significant digits grows faster than any polynomial in $n$ . Moreover, this input signal can easily and explicitly be generated from the given system parameters by a Turing machine. It is also shown that standard techniques for simulating higher-order LTI systems with real poles show the same complexity blowup. Finally, it is shown that a similar complexity blowup occurs for the calculation of Fourier series approximations and Fourier transforms.

A 2004 paper had offered a theoretical proof that ideally the roots of the minimum variance distortionless response (MVDR) beamformer array polynomial lie on the unit circle (UC). However, existing MVDR methods fail to exploit this fundamental property adequately. This paper proposes a new adaptive beamforming design via UC roots optimization for uniform linear arrays (ULA). The proposed method starts with the sample matrix inversion (SMI) roots and optimizes the MVDR criterion for each root separately by splitting the $N$ -dimensional MVDR problem into multiple 1-D optimization problems. Conjugate symmetry is imposed on individual 1st-order factors of the MVDR polynomial during optimization that guarantees UC roots. The proposed UC Roots Constrained MVDR (UCRC-MVDR) method is non-iterative and has a closed-form solution. It also works well with limited number of snapshots. UCRC-MVDR is computationally efficient and parallelizable as all roots can be optimized concurrently. In extensive simulation studies, UCRC-MVDR exhibits consistently superior performance over existing MVDR approaches, and its performance is closer to the ideal clairvoyant case than existing MVDR methods.

The causality analysis of multivariate time series and formation of complex networks relies on the estimation of the direct cause-effect from one observed variable to another accounting for the presence of other observed variables. Such effects are quantified by the conditional Granger causality index (CGCI), derived by linear vector autoregressive models (VAR). Dimension reduction approaches have been developed to restrict VAR models, such as the modified backward-in-time selection method (mBTS) giving the restricted CGCI (rCGCI). The rCGCI is limited to linear systems. In this study, we extend the mBTS dimension reduction scheme to polynomial VAR, so as to model nonlinear dynamics and cause-effect relationships and derive the Granger causality measure termed restricted polynomial CGCI (rpCGCI). The complications in the adaptation of mBTS to the restricted polynomial VAR and the construction of the Granger causality index are addressed, involving also a randomization significance test in the steps of mBTS. The rpCGCI has the advantage against other nonlinear Granger causality measures that it can be applied to short time series of high dimension (many observed variables). The simulation study on different types of multivariate stochastic processes and different lengths of generated time series showed the superiority of the proposed rpCGCI as compared to CGCI, rCGCI, pCGCI (using polynomial VAR) and other nonlinear causality measures. Further, rpCGCI was compared favorably to the other measures on signals of heart rate variability, respiration, and oxygen concentration in the blood, as well as multi-channel scalp electroencephalogram (EEG) recordings of epileptic patients containing epileptiform discharges.

Joint source and sensor localization is a challenging problem, nevertheless it has numerous potential applications. This paper takes time of flight measurements and develops an approximate and yet reasonably accurate algebraic solution to the problem by converting it to the identification of an upper triangular linear transformation matrix in the localization space. The proposed solution is in closed-form and not iterative, and it reduces the solution evaluation to the positive root of a polynomial of degree 3 or less. It is among the first in solving the problem when the source and/or sensor positions can be embedded in a lower dimensional space than the localization space, leading to a complete and robust solution. The solution derivation establishes naturally the conditions for the solvability of the localization problem. The resulting solution is sufficiently close to the optimum estimate and gives better results than those from the literature. Iterative refinement of the proposed solution on the source and sensor positions provides the Cramer-Rao Lower Bound accuracy under Gaussian noise with sufficient number of sources and sensors. Performance evaluation using the data from two experiments under real environment confirms the reliability and promising behavior of the proposed solutions.

The concept of paraunitary (PU) matrices arose in the early 1990 s in the study of multi-rate filter banks. These matrices have found wide applications in cryptography, digital signal processing, and wireless communications. Existing PU matrices are subject to certain constraints on their existence and hence their availability is not guaranteed in practice. Motivated by this, for the first time, we introduce a novel concept, called $Z$ -paraunitary (ZPU) matrix, whose orthogonality is defined over a matrix of polynomials with identical degree not necessarily taking the maximum value. We show that there exists an equivalence between a ZPU matrix and a $Z$ -complementary code set when the latter is expressed as a matrix with polynomial entries. Furthermore, we investigate some important properties of ZPU matrices, which are useful for the extension of matrix sizes and sequence lengths. We propose a new construction framework for optimal ZPU matrices which includes existing PU matrices as special cases. Finally, we give the enumeration formula for the constructed $Z$ -complementary sequences from the optimal ZPU matrices.

Graph filters play an important role in graph signal processing, in which the data is analyzed with respect to the underlying network (graph) structure. As an extension to classical signal processing, graph filters are generally constructed as a polynomial (FIR), or a rational (IIR) function of the underlying graph operator, which can be implemented via successive shifts on the graph. Although the graph shift is a localized operation, it requires all nodes to communicate synchronously, which can be a limitation for large scale networks. To overcome this limitation, this study proposes a node-asynchronous implementation of rational filters on arbitrary graphs. In the proposed algorithm nodes follow a randomized collect-compute-broadcast scheme: if a node is in the passive stage it collects the data sent by its incoming neighbors and stores only the most recent data. When a node gets into the active stage at a random time instance, it does the necessary filtering computations locally, and broadcasts a state vector to its outgoing neighbors. For the analysis of the algorithm, this study first considers a general case of randomized asynchronous state recursions and presents a sufficiency condition for its convergence. Based on this result, the proposed algorithm is proven to converge to the filter output in the mean-squared sense when the filter, the graph operator and the update rate of the nodes satisfy a certain condition. The proposed algorithm is simulated using rational and polynomial filters, and its convergence is demonstrated for various different cases, which also shows the robustness of the algorithm to random communication failures.

This paper deals with the NP-hard quadratic optimization problem under similarity and constant modulus constraints. A computationally efficient iterative algorithm based on the Alternating Direction Penalty Method (ADPM) framework is proposed for continuous and discrete phase cases. In each iteration, it converts the considered problem into two subproblems with closed-form solutions via an introduced auxiliary variable, while locally increasing the penalty factor involved in the ADPM framework. The proposed algorithm is proven to converge for any initialization under some mild conditions and avoids the non-convergence problem of the Alternating Direction Method of Multipliers (ADMM) when handling the NP-hard problems. It ensures that the obtained solution fulfills the Karush-Kuhn-Tucker (KKT) conditions for the continuous phase case. To further refine the ADPM solution, a joint approach involving both the ADPM and the coordinate descent frameworks is introduced. The extension that solves the quadratic optimization problem incorporating more complicated constraints is also developed. Finally, two radar waveform design examples are presented to demonstrate that the proposed algorithms can outperform their counterparts by providing better objective values with relatively low polynomial computational complexities.

The unprecedented elevation of wireless technologies produces the ever-increasing requirement for higher-dimensional array sets with preferable correlation properties and more flexible parameters. In this paper, we investigate new two-dimensional $Z$ -complementary array code sets (2D-ZCACSs) with unimodular arrays, which are more preferable in ultra wideband communication system to improve its performance than 2D mutually orthogonal complementary array set. We first introduce a new idea of 2D $Z$ -paraunitary (2D-ZPU) matrices by extending our previous concept of 1D-ZPU matrices. Then, we show that there exists an equivalence between a 2D-ZCACS and 2D-ZPU matrix when the former is expressed as a matrix with 2D generating polynomial entries. In the 2D generating matrix, each column corresponds to a 2D $Z$ -complementary array code and two distinct columns correspond to 2D $Z$ -complementary array mates. Finally, we propose a new construction method of unimodular 2D-ZCACSs with the aid of higher-dimensional $z$ -transforms and the theory of ZPU matrices.

Channel coding technology is indispensable in digital communication systems. In noncooperative contexts, the blind identification of channel codes is very important. In this paper, a new algorithm that directly uses a soft-decision sequence for blind reconstruction of cyclic codes is proposed. From the algebraic structure of cyclic codes, we deduce that a cyclic code of length n must be able to divide the polynomial xn + 1, and the dual spaces corresponding to the factors of the generator polynomial can form a parity-check relation with the code words. In order to detect this relation, the concept of the average cosine conformity is defined, which can fully utilize the intercepted soft-decision sequence to measure the reliability of the parity-check relation. Further, the statistical characteristics of the average cosine conformity with respect to a candidate factor of the generator polynomial are analyzed in detail. When the traversal code length n is equal to the actual length, some factors in xn + 1 allow this constraint relation to be detected, and the generator polynomial of the cyclic codes consists of these factors. Hence, the blind reconstruction of the cyclic code is exactly equivalent to the hypothesis testing problem. Simulations show that the derived theoretical distribution of the average cosine conformity is consistent with the simulation results. Moreover, the proposed algorithm has preferable performance at low signal-to-noise ratios compared with existing methods, and its computational complexity is reasonable.

Euclidean distance matrices (EDMs) are a major tool for localization from distances, with applications ranging from protein structure determination to global positioning and manifold learning. They are, however, static objects which serve to localize points from a snapshot of distances. If the objects move, one expects to do better by modeling the motion. In this paper, we introduce Kinetic Euclidean Distance Matrices (KEDMs)& x2014;a new kind of time-dependent distance matrices that incorporate motion. The entries of KEDMs become functions of time, the squared time-varying distances. We study two smooth trajectory models & x2014;polynomial and bandlimited trajectories & x2014;and show that these trajectories can be reconstructed from incomplete, noisy distance observations, scattered over multiple time instants. Our main contribution is a semidefinite relaxation, inspired by similar strategies for static EDMs. Similarly to the static case, the relaxation is followed by a spectral factorization step; however, because spectral factorization of polynomial matrices is more challenging than for constant matrices, we propose a new factorization method that uses anchor measurements. Extensive numerical experiments show that KEDMs and the new semidefinite relaxation accurately reconstruct trajectories from noisy, incomplete distance data and that, in fact, motion improves rather than degrades localization if properly modeled. This makes KEDMs a promising tool for problems in geometry of dynamic points sets.

In this paper, we design constant modulus probing waveforms with good correlation properties for collocated multi-input multi-output (MIMO) radar systems. The main content is as follows: first, we formulate the design problem as a fourth order polynomial minimization problem with constant modulus constraints. Then, by exploiting introduced auxiliary variables and their inherent structures, the polynomial optimization model is equivalent to a non-convex consensus minimization problem. Second, a customized alternating direction method of multipliers (ADMM) algorithm is proposed to solve the non-convex problem approximately. In the algorithm, all the subproblems can be solved analytically. Moreover, all subproblems except one subproblem can be performed in parallel. Third, we prove that the customized ADMM algorithm is theoretically-guaranteed convergent if proper parameters are chosen. Fourth, two variant ADMM algorithms, based on stochastic block coordinate descent and accelerated gradient descent, are proposed to reduce computational complexity and speed up the convergence rate. Numerical examples show the effectiveness of the proposed consensus-ADMM algorithm and its variants., Comment: 16pages,6 figures. This work was presented in part at 2018 International Conference on Acoustics, Speech and Signal Processing (ICASSP) in Calgary, Alberta, Canada

We consider the problem of anomaly detection among $K$ heterogeneous processes. At each given time, one process is probed, and the random observations follow two different distributions, depending on whether the process is normal or abnormal. Each anomalous process incurs a cost until its anomaly is identified and fixed, and the cost is a nonlinear (specifically, polynomial with degree $d$ ) function of the duration of the anomalous state. The objective is a sequential search strategy that minimizes the total expected cost incurred by all the processes during the detection process under reliability constraints. We propose a search algorithm that consists of exploration, exploitation, and sequential testing phases. We establish its asymptotic optimality and analyze the approximation ratio and the regret under computational constraints.

Digital filter transfer functions can be converted between the direct form and parallel connections of elementary sections, typically second-order (“biquad”) sections. The conversion from direct to parallel form is performed using a partial fraction expansion, which usually requires long division of polynomials when expanding proper and improper transfer functions. This paper focuses on the conversion of a series of biquad sections to the parallel form, and proposes a novel way to implement the partial-fraction expansion without the use of long division. Additionally, the resulting structure is the delayed parallel form in which the section gains remain small. The new design and previous methods are compared in a case study on graphic equalizer design. The delayed parallel filter is shown to use the same number of operations as the series form during filtering. The conversion of a recently proposed series graphic equalizer into the delayed parallel form leads to an improved parallel graphic equalizer design relative to all known prior approaches. The proposed conversion technique is widely applicable to the design of parallel infinite impulse response filters, which are becoming popular as they are well suited to implementation using parallel computers.

This paper introduces a node-asynchronous communication protocol in which an agent in a network wakes up randomly and independently, collects states of its neighbors, updates its own state, and then broadcasts back to its neighbors. This protocol differs from consensus algorithms and it allows distributed computation of an arbitrary eigenvector of the network, in which communication between agents is allowed to be directed. (The graph operator is still required to be a normal matrix). To analyze the scheme, this paper studies a random asynchronous variant of the power iteration. Under this random asynchronous model, an initial signal is proven to converge to an eigenvector of eigenvalue 1 (a fixed point) even in the case of operator having spectral radius larger than unity. The rate of convergence is shown to depend not only on the eigenvalue gap but also on the eigenspace geometry of the operator as well as the amount of asynchronicity of the updates. In particular, the convergence region for the eigenvalues gets larger as the updates get less synchronous. Random asynchronous updates are also interpreted from the graph signal perspective, and it is shown that a non-smooth signal converges to the smoothest signal under the random model. When the eigenvalues are real, second order polynomials are used to achieve convergence to an arbitrary eigenvector of the operator. Using second order polynomials the paper formalizes the node-asynchronous communication model. As an application, the protocol is used to compute the Fiedler vector of a network to achieve autonomous clustering.

Newton's method is a widely applicable and empirically efficient method for finding the solution to a set of equations. The recently developed algebraic geometry analyses provide information-theoretic bounds on the sampling rate to ensure the existence of a unique completion. A remained open question from these works is to retrieve the sampled data when the sampling rate is very close to the mentioned information-theoretic bounds. This paper is concerned with proposing algorithms to retrieve the sampled data when the sampling rate is too small and close to the mentioned information-theoretic bounds. Hence, we propose a new approach for recovering a partially sampled low-rank matrix or tensor when the number of samples is only slightly more than the dimension of the corresponding manifold, by solving a set of polynomial equations using Newton's method. In particular, we consider low-rank matrix completion, matrix sensing, and tensor completion. Each observed entry contributes one polynomial equation in terms of the factors in the rank factorization of the data. By exploiting the specific structures of the resulting set of polynomial equations, we analytically characterize the convergence regions of the Newton's method for matrix completion and matrix sensing. Through extensive numerical results, we show that the proposed approach outperforms the well-known methods such as nuclear norm minimization and alternating minimization in terms of the success rate of data recovery (noiseless case) and peak signal-to-noise ratio (noisy case), especially when the sampling rate is very low.

The extremal values of multivariate trigonometric polynomials are of interest in fields ranging from control theory to filter design, but finding the extremal values of such a polynomial is generally NP-Hard. In this paper, we develop simple and efficiently computable estimates of the extremal values of a multivariate trigonometric polynomial directly from its samples. We provide an upper bound on the modulus of a complex trigonometric polynomial, and develop upper and lower bounds for real trigonometric polynomials. For a univariate polynomial, these bounds are tighter than existing bounds, and the extension to multivariate polynomials is new. As an application, the lower bound provides a sufficient condition to certify global positivity of a real trigonometric polynomial.

Recovery of certain piecewise continuous signals from noisy observations has been a major challenge in sciences and engineering. In this paper, in a tight-dimensional representation space, we exploit sparsity hidden in a class of possibly discontinuous signals named finite-dimensional piecewise continuous (FPC) signals. More precisely, we propose a tight-dimensional linear transformation which reveals a certain sparsity in discrete samples of the FPC signals. This transformation is designed by exploiting the fact that most of the consecutive samples are contained in special subspaces. Numerical experiments on recovery of piecewise polynomial signals and piecewise sinusoidal signals show the effectiveness of the revealed sparsity.

Processing of signals with irregular structures is a fundamental challenge to the conventional signal processing due to the complex structures. Since most of the relationships among such data from engineering applications are inherently nonlinear, those tools that do not take the nonlinearity into account may have limitations in dealing with such relationships. In this paper, a novel nonlinear polynomial graph filter (NPGF) is proposed to facilitate the nonlinear processing of signals with irregular structures. First of all, the nonlinear relationship between the input and output graph signals is constructed, which is further developed to utilize the structure information of the irregular structures (i.e., the graph shift ${\boldsymbol S}$ ). Specifically, the nonlinear kernels and the nonlinear input terms are both designed to be polynomials of the graph shift ${\boldsymbol S}$ . Such nonlinear polynomial relationship is then defined as the NPGF. Note that shift invariance is a fundamental property in signal processing but is not straightforward in the existing nonlinear graph signal processing techniques. Due to the special expression of the NPGF, the shift-invariance is extended to our NPGF, which can conveniently facilitate the analysis and design of graph signals using NPGF and is one of the most important contributions in this paper. Numerical studies that characterize the nonlinear temperature distribution and GDP prediction based on real datasets are presented. Compared with other existing techniques, our NPGF achieves superior capability in characterizing the nonlinear relationship between the input and output graph signals, especially when only very few graph signals can be observed.

Traditional sampling results assume that the sample locations are known. Motivated by simultaneous localization and mapping (SLAM) and structure from motion (SfM), we investigate sampling at unknown locations. Without further constraints, the problem is often hopeless. For example, we recently showed that, for polynomial and bandlimited signals, it is possible to find two signals, arbitrarily far from each other, that fit the measurements. However, we also showed that this can be overcome by adding constraints to the sample positions. In this paper, we show that these constraints lead to a uniform sampling of a composite of functions. Furthermore, the formulation retains the key aspects of the SLAM and SfM problems, whilst providing uniqueness, in many cases. We demonstrate this by studying two simple examples of constrained sampling at unknown locations. In the first, we consider sampling a periodic bandlimited signal composite with an unknown linear function. We derive the sampling requirements for uniqueness and present an algorithm that recovers both the bandlimited signal and the linear warping. Furthermore, we prove that, when the requirements for uniqueness are not met, the cases of multiple solutions have measure zero. For our second example, we consider polynomials sampled such that the sampling positions are constrained by a rational function. We previously proved that, if a specific sampling requirement is met, uniqueness is achieved. In addition, we present an alternate minimization scheme for solving the resulting non-convex optimization problem. Finally, fully reproducible simulation results are provided to support our theoretical analysis.

Signal processing applications of semidefinite optimization are often rooted in sum-of-squares representations of nonnegative trigonometric polynomials. Interior-point solvers for semidefinite optimization can handle constraints of this form with a per-iteration-complexity that is cubic in the degree of the trigonometric polynomial. The purpose of this paper is to discuss first-order methods with a lower complexity per iteration. The methods are based on generalized proximal operators defined in terms of the Itakura–Saito distance. This is the Bregman distance defined by the negative entropy function. The choice for the Itakura–Saito distance is motivated by the fact that the associated generalized projection on the set of normalized nonnegative trigonometric polynomials can be computed at a cost that is roughly quadratic in the degree of the polynomial. The generalized projection is the key operation in generalized proximal first-order methods that use Bregman distances instead of the squared Euclidean distance. The paper includes numerical results with Auslender and Teboulle's accelerated proximal gradient method for Bregman distances.

Cascade dynamic nonlinear systems can describe a wide class of engineering problems, but little efforts have been devoted to the identification of such systems so far. One of the difficulties comes from its non-convex characteristic. In this paper, the identification of a general cascade dynamic nonlinear system is rearranged and transformed into a convex problem involving a double-input single-output nonlinear system. In order to limit the estimate error at the frequencies of interest and to overcome the singularity problem incurred in the least-square-based methods, the identification problem is, thereafter, decomposed into a multi-objective optimization problem, in which the objective functions are defined in terms of the spectra of the unbiased error function at the frequencies of interest and are expressed as a first-order polynomial of the model parameters to be identified. The coefficients of the first-order polynomial are derived in an explicit expression involving the system input and the measured noised output. To tackle the convergence performance of the multi-objective optimization problem, the bargaining game theory is used to model the interactions and the competitions among multiple objectives defined at the frequencies of interest. Using the game-theory-based approach, both the global information and the local information are taken into account in the optimization, which leads to an obvious improvement of the convergence performance. Numerical studies demonstrate that the proposed bargaining-game-theory-based algorithm is effective and efficient for the multi-objective optimization problem, and so is the identification of the cascade dynamic nonlinear systems.

This paper investigates the relay hybrid precoding design in millimeter-wave massive multiple-input multiple-output systems. The optimal design of the relay hybrid precoding is highly nonconvex, due to the six-order polynomial objective function, six-order polynomial constraint, and constant-modulus constraints. To efficiently solve this challenging nonconvex problem, we first reformulate it into three quadratic subproblems, where one of the subproblems is convex and the other two are nonconvex. Then, we propose an iterative successive approximation (ISA) algorithm to attain the high-approximate optimal solution to the original problem. Specifically, in the proposed ISA algorithm, we first convert the two nonconvex subproblems to convex ones by the relaxation of the constant-modulus constraints, and then we solve the three corresponding convex subproblems iteratively. We theoretically prove that the ISA algorithm converges to a Karush–Kuhn–Tucker point of the original problem. Simulation results demonstrate that the proposed ISA algorithm achieves good performance in terms of achievable rate in both full-connected and subconnected relay hybrid precoding systems.

We address the problem of sampling and reconstruction of sparse signals with finite rate of innovation. We derive general conditions under which perfect reconstruction is possible for sampling kernels satisfying Strang-Fix conditions. Previous results on the subject consider two particular cases; when the kernel is able to reproduce (complex) exponentials, or when it has the polynomial reproduction property. In this paper, we extend such analysis to the case where both properties could be found in the sampling kernel and show that the former two situations can be regarded as special cases. As a result of our analysis, we provide general conditions under which perfect recovery in the noiseless case is possible. In practice, a given sampling kernel might not satisfy Strang-Fix conditions. When dealing with arbitrary sampling kernels, we propose a unified view for sampling and reconstruction in the frequency domain. Our formulation generalizes previous approaches and provides new insights for devising optimal reconstruction schemes. We also propose a novel algorithm for denoising treating the problem as a particular instance of structured low-rank approximation. Finally, we provide some numerical experiments and a comparison between different state-of-the-art methods showing the improved estimation performance of the proposed approach.

In graph signal processing, filters arise from polynomials in shift matrices that respect the graph structure, such as the graph adjacency matrix or the graph Laplacian matrix. Hence, filter design for graph signal processing benefits from knowledge of the spectral decomposition of these matrices. Often, stochastic influences affect the network structure and, consequently, the shift matrix empirical spectral distribution. Although the joint distribution of the shift matrix eigenvalues is typically inaccessible, deterministic functions that asymptotically approximate the matrix empirical spectral distribution can be found for suitable random graph models using tools from random matrix theory. We employ this information regarding the density of eigenvalues to develop criteria for optimal graph filter design. In particular, we consider filter design for distributed average consensus and related problems, leading to improvements in short-term error minimization or in asymptotic convergence rate.

We study the optimal design of graph filters (GFs) to implement arbitrary linear transformations between graph signals. GFs can be represented by matrix polynomials of the graph-shift operator (GSO). Since this operator captures the local structure of the graph, GFs naturally give rise to distributed linear network operators. In most setups, the GSO is given so that GF design consists fundamentally in choosing the (filter) coefficients of the matrix polynomial to resemble desired linear transformations. We determine spectral conditions under which a specific linear transformation can be implemented perfectly using GFs. For the cases where perfect implementation is infeasible, we address the optimization of the filter coefficients to approximate the desired transformation. Additionally, for settings where the GSO itself can be modified, we study its optimal design as well. After this, we introduce the notion of a node-variant GF, which allows the simultaneous implementation of multiple (regular) GFs in different nodes of the graph. This additional flexibility enables the design of more general operators without undermining the locality in implementation. Perfect and approximate designs are also studied for this new type of GFs. To showcase the relevance of the results in the context of distributed linear network operators, this paper closes with the application of our framework to two particular distributed problems: finite-time consensus and analog network coding.

We propose two computationally efficient residual Doppler shift estimation methods for underwater acoustic multicarrier communication. The first method is based on computing the phase of the root of a low order polynomial. The second method is a closed-form least squares estimate given the unwrapped phases of the minimal eigenvector of a small data matrix. The complexities of both estimates are significantly lower compared to the methods commonly used in underwater acoustic multicarrier communication, which result in nonlinear least squares estimators and thus require a fine grid search in the frequency domain. Numerical simulations show that the mean square errors of the proposed methods have similar performance as the common estimation techniques, achieve the Cramer–Rao lower bounds at low noise levels, and agree with their theoretically derived variances. Pool experiments and sea trial results further demonstrate that the suggested estimates yield similar results as the common nonlinear least squares estimates but at a lower complexity.

In this paper, we derive closed-form and near closed-form solutions for joint source and sensor localization from time-difference-of-arrival (TDOA) measurements. In our previous works, we derived closed-form and near closed-form solutions for joint source and sensor localization from time-of-arrival (TOA) measurements. On the basis of these results, the main idea in this paper is to recover the TOA information only from the given TDOA measurements. We show that the TOA information can be recovered by using the low-rank property of the difference of square TOA-distance matrix in a closed-form or a near closed-form based on the linear method of solving polynomial equations. Since the low-rank property is reliable even in noisy cases, the TOA recovery works well under both small and large amounts of noise. The root-mean-squared errors achieved by our proposed algorithms are compared with the Cramer–Rao lower bound in synthetic experiments. The results show that the proposed methods work well for both small and large amounts of noise and for small and large numbers of sources and sensors.

This paper considers parameter estimation of multicomponent 2D polynomial-phase signals (mc-2D PPSs). The main contributions included are: i) Derivation of the Cramer-Rao lower bound (CRLB) for mc-2D PPSs; ii) Two dimensional product high-order ambiguity function (2D PHAF) based estimation procedure, recently proposed by Barbarossa, for the estimation of third-order mc-2D PPSs is extended to signals of arbitrary orders; iii) Procedure for optimal lag set selection in the proposed 2D PHAF has been proposed; iv) Since the 2D PHAF is characterized by large mean squared error (MSE) for higher-order signals, refinement procedure is introduced that is able to improve the estimation accuracy and to reduce MSE up to the CRLB. The proposed estimator has been used for target focusing in radar images.

Traditional quadratic time-frequency distributions are not designed to deal with randomly undersampled signals or data with missing samples. The compressed data measurements introduce noise-like artifacts in the ambiguity domain, compounding the problem of separating the signal auto-terms and cross-terms. In this paper, we propose a multi-task kernel design for suppressing both the artifacts and the cross-terms, while preserving the signal desirable auto-terms. The proposed approach results in highly concentrated time-frequency signature. We evaluate our approach using various polynomial phase signals and show its benefits, especially in the case of strong artifacts.

For parahermitian polynomial matrices, which can be used, for example, to characterise space-time covariance in broadband array processing, the conventional eigenvalue\ud decomposition (EVD) can be generalised to a polynomial matrix EVD (PEVD). In this paper, a new iterative PEVD algorithm based on sequential matrix diagonalisation (SMD) is introduced. At every step the SMD algorithm shifts the dominant column or row of the polynomial matrix to the zero lag position and eliminates the resulting instantaneous correlation. A proof of convergence is provided, and it is demonstrated that SMD establishes diagonalisation faster and with lower order operations than existing PEVD algorithms.

Two adaptive Capon methods that jointly estimate the azimuth-angle and polarization of the sources in a closed-form are proposed. It is shown that the azimuth-angles of the sources may be estimated from the roots of a complex-valued polynomial or by rooting a real-valued polynomial, instead. The latter method is particularly useful in tracking arbitrarily polarized sources in a sequential snapshot-by-snapshot manner using root-tracking techniques. The proposed polynomial rooting based methods are applicable to polarization sensitive arrays regardless of the array geometry including conformal arrays, and take into account array nonidealities. A large-sample analysis of the polarimetric Capon method is also provided showing that it converges, up to a multiplicative factor that depends on the interference-plus-noise power, to the polarimetric MUSIC method in the high SINR regime. Such a result gives a new insight into the well-known Capon and MUSIC methods. This paper also shows that employing manifold separation in robust Capon beamforming as well as in transmit beamforming schemes leads to improved performance in terms of received SINR when array calibration measurements are used. Extensive numerical results employing real-world polarimetric arrays are given. Results show that employing manifold separation leads to improved performance in many array processing tasks.

The deterministic identification of Hammerstein systems is investigated in this paper. Based on the over-sampling technique, a new deterministic identification approach is presented, which blindly identifies the linear dynamic part followed by the estimation of the nonlinear function. The proposed method allows us to identify the Hammerstein system using an over-sampling rate smaller than the numerator polynomial's length of the linear dynamic part as required by other existing methods. In addition, it can obtain the true values of the system parameters in the noise-free case and an asymptotically consistent estimate in the presence of noise. The richness condition of the system input and the selection of the over-sampling rate are studied for the identifiability of the Hammerstein system. Simulation examples are given to show the performance of the proposed method.

This paper extends the existing fast RLS recursions originally intended to exponentially windowed problems for general models, to a generalized sliding window formulation (GSWRLS). From a matrix algebra perspective, we show explicitly how the displacement rank of the underlying inverse covariance matrix associated to any operator is defined as a function of the number of window breakpoints and how the fast GSWRLS calculates these rank factors in a fast manner. The recursions hold regardless of the (first order) data structure induced and show that fast fixed order and order recursive RLS algorithms can still be obtained for unwindowed data matrices exhibiting a fixed arbitrary relation between successive regressors. Our approach highlights the existence of a certain degree of freedom inherent to structured data matrices induced by general models, showing that efficient representations of their inverse covariances are not limited to factor circulants, but rather constructed from any arbitrary operator. These Bezoutians, usually expressed via reproducing kernel relations, can be represented exactly in matrix form, along with a precise correspondence to variables of a GSWRLS. As a fallout, we obtain a vector relation stating the so-called minimality property, for extended models and windows, as opposed to analogous generating function arguments normally seen in original approaches. These results pave the way to a more general framework of polynomial Vandermonde covariance decompositions which arise naturally via a proper choice of recurrence related polynomials. This has further impact on several signal processing applications, including superfast realization of equalizers in communications scenarios.

Real number block codes derived from the discrete cosine transform (DCT) are corrupted by a few large errors along with low-level noise. Checking syndromes are encapsulated in Laurent polynomials and a special Euclidean algorithm determines the locations of large errors. These locations are adjusted properly to give an error-modeling polynomial that is used to extend syndromes which are in turn transformed to codeword error values. A probabilistic analysis describes the effects of the low-level noise on corrected values after they pass through the syndrome extension process. Simulations yield probability of codeword errors, mean-squared decoding errors and sample means and variances of low-level noise effects.

This paper addresses the problem of estimating simultaneously a local polynomial signal and an approximately piecewise constant signal from a noisy additive mixture. The approach developed in this paper synthesizes the total variation filter and least-square polynomial signal smoothing into a unified problem formulation. The method is based on formulating an l1-norm regularized inverse problem. A computationally efficient algorithm, based on variable splitting and the alternating direction method of multipliers (ADMM), is presented. Algorithms are derived for both unconstrained and constrained formulations. The method is illustrated on experimental data involving the detection of nano-particles with applications to real-time virus detection using a whispering-gallery mode detector.

In this paper, we consider parameter estimation of high-order polynomial-phase signals (PPSs). We propose an approach that combines the cubic phase function (CPF) and the high-order ambiguity function (HAF), and is referred to as the hybrid CPF-HAF method. In the proposed method, the phase differentiation is first applied on the observed PPS to produce a cubic phase signal, whose parameters are, in turn, estimated by the CPF. The performance analysis, carried out in the paper, considers up to the tenth-order PPSs, and is supported by numerical examples revealing that the proposed approach outperforms the HAF in terms of the accuracy and signal-to-noise-ratio threshold. Extensions to multicomponent and multidimensional PPSs are also considered, all supported by numerical examples. Specifically, when multicomponent PPSs are considered, the product version of the CPF-HAF outperforms the product HAF (PHAF) that fails to estimate parameters of components whose PPS order exceeds three.

This correspondence presents a new second-order statistical approach to blind identification of single-input multiple-output (SIMO) autoregressive and moving average (ARMA) system models. The proposed approach exploits the dynamical autoregressive information of the model contained in the autocorrelation matrices of the system outputs but does not require the block Toeplitz structure of the channel convolution matrix used by classical subspace methods. For the multi-channel model with the same autoregressive (AR) polynomial, sufficient conditions and an efficient identification algorithm are given such that the multi-channel model can be uniquely identified up to a constant scaling factor. Furthermore, an extension of the result to blind identification of multi-channel models with different AR polynomials is presented. Simulation results are given to show the effectiveness of the proposed approach.

This paper investigates the computationally efficient parameter estimation of polynomial phase signals embedded in noise. Many authors have previously proposed multilinear analysis methods which operate on uniformly spaced samples of the signal. Such methods include the higher-order ambiguity functions (HAFs), the Polynomial Wigner-Ville distributions (PWVDs) and the higher-order phase (HP) functions. This paper investigates the use of multilinear methods which operate on nonuniformly spaced signal samples. It is seen that the relaxation of the requirement to use uniformly spaced samples in the analysis can lead to significant performance improvements. A theoretical analysis and simulations are presented in support of these claims.

This paper presents new Compact-based kernel high-resolution TFDs which outperform other well known classical TFDs in terms of crossterms reduction while still achieving the best time-frequency resolution and then preserving high energy concentration around the components’ instantaneous frequencies. (Additional details can be found in the comprehensive book on Time-Frequency Signal Analysis and Processing (see http://www.elsevier.com/locate/isbn/0080443354). In addition, the most recent upgrade of the original software package that calculates Time-Frequency Distributions and Instantaneous Frequency estimators can be downloaded from the web site: www.time-frequency.net. This was the first software developed in the field, and it was first released publicly in 1987 at the 1st ISSPA conference held in Brisbane, Australia, and then continuously updated). This paper presents two new time-frequency distributions (TFDs) based on kernels with compact support (KCS) namely the separable (CB) (SCB) and the polynomial CB (PCB) TFDs. The implementation of this family of TFDs follows the method developed for the Cheriet-Belouchrani (CB) TFD. The mathematical properties of these three TFDs are analyzed and their performance is compared to the best classical quadratic TFDs using several tests on multi-component signals with linear and nonlinear frequency modulation (FM) components including the noise effects. Instead of relying solely on visual inspection of the time-frequency domain plots, comparisons include the time slices’ plots and the evaluation of the Boashash-Sucic’s normalized instantaneous resolution performance measure that permits to provide the optimized TFD using a specific methodology. In all presented examples, the KCS-TFDs show a significant interference rejection, with the component energy concentration around their respective instantaneous frequency laws yielding high resolution measure values.

International audience; Empirical Mode Decomposition (EMD) is a relatively new method for adaptive multiscale signal representation. As it allows to adaptively analyze nonlinear and non-stationary signals, it is widely used in signal processing. Yet, as the standard EMD method lacks a solid mathematical background, many alternative constructions have been proposed to define similar decompositions in a more comprehensive way. This paper is in line with this idea, as it defines a new decomposition that lies on direct constrained optimization. We show that this new approach gives satisfactory results for narrow-band signals and preserves the essential characteristics of the original EMD

In the present paper, we propose a novel method for estimating one-dimensional damped and undamped harmonics. Our method utilizes the multiple shift-invariance property comprised in the signal model. We develop a new rank-reduction estimator which is formed as the weighted sum of the individual matrix polynomials obtained from individual shift-invariance equations. The uniqueness conditions for the proposed rank-reduction criteria are derived under the assumption that all samples are available. Moreover, a novel technique for the incomplete data case, where some samples are missing, is presented. In this case, the rank-reduction estimator may suffer from ambiguities. To overcome this problem, we propose an extension of the rank-reduction estimator that is based on polynomial intersection and the properties of the Sylvester matrix. The latter algorithm yields unique estimates of the damped harmonics. The proposed high-resolution techniques are search-free and therefore, they enjoy moderate computational complexity.

Volterra and polynomial regression models play a major role in nonlinear system identification and inference tasks. Exciting applications ranging from neuroscience to genome-wide association analysis build on these models with the additional requirement of parsimony. This requirement has high interpretative value, but unfortunately cannot be met by least-squares based or kernel regression methods. To this end, compressed sampling (CS) approaches, already successful in linear regression settings, can offer a viable alternative. The viability of CS for sparse Volterra and polynomial models is the core theme of this work. A common sparse regression task is initially posed for the two models. Building on (weighted) Lasso-based schemes, an adaptive RLS-type algorithm is developed for sparse polynomial regressions. The identifiability of polynomial models is critically challenged by dimensionality. However, following the CS principle, when these models are sparse, they could be recovered by far fewer measurements. To quantify the sufficient number of measurements for a given level of sparsity, restricted isometry properties (RIP) are investigated in commonly met polynomial regression settings, generalizing known results for their linear counterparts. The merits of the novel (weighted) adaptive CS algorithms to sparse polynomial modeling are verified through synthetic as well as real data tests for genotype-phenotype analysis., 20 pages, to appear in IEEE Trans. on Signal Processing

Consider the problem of estimating the parameters of multiple polynomial phase signals observed by a sensor array. In practice, it is difficult to maintain a precisely calibrated array. The array manifold is then assumed to be unknown, and the estimation is referred to as blind estimation. To date, only an approximated maximum likelihood estimator (AMLE) was suggested for blindly estimating the polynomial coefficients of each signal. However, this estimator requires a multidimensional search over the entire coefficient space. Instead, we propose an estimation approach which is based on two steps. First, the signals are separated using a blind source separation technique, which exploits the constant modulus property of the signals. Then, the coefficients of each polynomial are estimated using a least squares method applied to the unwrapped phase of the estimated signal. This estimator does not involve any search in the coefficient spaces. The computational complexity of the proposed estimator increases linearly with respect to the polynomial order, whereas that of the AMLE increases exponentially. Simulation results show that the proposed estimator achieves the Cramer-Rao lower bound at moderate or high signal to noise ratio.

We explore the feasibility of interference alignment in signal vector space-based only on beamforming-for K-user MIMO interference channels. Our main contribution is to relate the feasibility issue to the problem of determining the solvability of a multivariate polynomial system which is considered extensively in algebraic geometry. It is well known, e. g., from Bezout's theorem, that generic polynomial systems are solvable if and only if the number of equations does not exceed the number of variables. Following this intuition, we classify signal space interference alignment problems as either proper or improper based on the number of equations and variables. Rigorous connections between feasible and proper systems are made through Bernshtein's theorem for the case where each transmitter uses only one beamforming vector. The multibeam case introduces dependencies among the coefficients of a polynomial system so that the system is no longer generic in the sense required by both theorems. In this case, we show that the connection between feasible and proper systems can be further strengthened (since the equivalency between feasible and proper systems does not always hold) by including standard information theoretic outer bounds in the feasibility analysis.

This paper puts to use concepts and tools introduced in Part I to address a wide spectrum of noncausal sampling and reconstruction problems. Particularly, we follow the system-theoretic paradigm by using systems as signal generators to account for available information and system norms (L2 and L∞) as performance measures. The proposed optimization-based approach recovers many known solutions, derived hitherto by different methods, as special cases under different assumptions about acquisition or reconstructing devices (e.g., polynomial and exponential cardinal splines for fixed samplers and the Sampling Theorem and its modifications in the case when both sampler and interpolator are design parameters). We also derive new results, such as versions of the Sampling Theorem for downsampling and reconstruction from noisy measurements, the continuous-time invariance of a wide class of optimal sampling-and-reconstruction circuits, etcetera.