Search

Effective non-parametric density estimation is a key challenge in high-dimensional multivariate data analysis. In this paper, we propose a novel approach that builds upon tensor factorization tools. Any multivariate density can be represented by its characteristic function, via the Fourier transform. If the sought density is compactly supported, then its characteristic function can be approximated, within controllable error, by a finite tensor of leading Fourier coefficients, whose size depends on the smoothness of the underlying density. This tensor can be naturally estimated from observed and possibly incomplete realizations of the random vector of interest, via sample averaging. In order to circumvent the curse of dimensionality, we introduce a low-rank model of this characteristic tensor, which significantly improves the density estimate especially for high-dimensional data and/or in the sample-starved regime. By virtue of uniqueness of low-rank tensor decomposition, under certain conditions, our method enables learning the true data-generating distribution. We demonstrate the very promising performance of the proposed method using several toy, measured, and image datasets. [ABSTRACT FROM AUTHOR]

A sensor array collects spatial samples of propagating wave fields, and a beamformer performs spatial filtering to preserve the desired signal while suppressing interfering signals and noise arriving from directions other than the direction of interest. Given a signal with wideband frequency, using a uniform array is one of the most common approaches to obtain broadband beamforming. In this work, a function formulating the relations between the sensor coefficients and its beam pattern over frequency is introduced. The function is called inverse beam pattern transform. The inverse beam pattern transform mainly contains the coordinate transform and inverse Fourier transform. From the view of spatial aliasing, the inter-distance of the sensors should be less than half of the minimum wavelength of the signal. However, from the bijection of the new function and broadband beamforming perspective, this paper proposes the other lower and upper bounds for the inter-distance. Within these bounds, the new function is the bijective function which can be applied to design the uniform array with broadband beamforming. [ABSTRACT FROM AUTHOR]

In this paper, our goal is first to investigate the behavior of reassignment operators used in synchrosqueezing transforms applied to multicomponent signals made of the superposition of amplitude and frequency modulated modes. Indeed, while these operators are associated with instantaneous frequency estimators very accurate on specific types of modes, the quality of the former worsens drastically when the modes depart from the ideal case they are designed for. We show in this paper that this particularly true when the modes interfere in the time-frequency plane or when some noise is present. Based on that analysis, we propose a novel instantaneous frequency estimator that only makes use of some specific points located on the ridges of synchrosqueezing transforms, and compare its performance with state-of-the-art techniques based on the same type of time-frequency representations. [ABSTRACT FROM AUTHOR]

For theessential set of discrete prolate spheroidal sequences (DPSS) corresponding to a given discrete-time-bandwidth product, we show that the auto and cross-correlations between the member sequences of the set also exhibit high concentration over a correlation length twice the concentration length of the member sequences. We start by deriving one upper bound and two lower bounds for the energy of the correlation sequence of index-limited DPSSs from which we derive similar bounds for the energy of DPSS correlation sequences. Then, we obtain an upper bound for the tail energy of DPSS correlation sequences. Finally, we obtain a lower bound for the concentration ratio of DPSS correlation sequences. All derived bounds require knowledge of the following parameters for each DPSS sequence in the correlation pair: corresponding eigen-value, Fourier transform evaluated at two special frequency points, derivative of the Fourier transform evaluated at the same two points. Most of the aforementioned parameters can be expressed or bounded by functions in the global parameters: sequence length and discrete-time-bandwidth. [ABSTRACT FROM AUTHOR]

We consider the sparse phase retrieval problem of recovering a sparse signal $\mathbf {x}$ in $\mathbb {R}^d$ from intensity-only measurements in dimension $d \geq 2$. Sparse phase retrieval can often be equivalently formulated as the problem of recovering a signal from its autocorrelation, which is in turn directly related to the combinatorial problem of recovering a set from its pairwise differences. In one spatial dimension, this problem is well studied and known as the turnpike problem. In this work, we present MISTR (Multidimensional Intersection Sparse supporT Recovery), an algorithm which exploits this formulation to recover the support of a multidimensional signal from magnitude-only measurements. MISTR takes advantage of the structure of multiple dimensions to provably achieve the same accuracy as the best one-dimensional algorithms in dramatically less time. We prove theoretically that MISTR correctly recovers the support of signals distributed as a Gaussian point process with high probability as long as sparsity is at most $\mathcal {O}(n^{d\theta })$ for any $\theta < 1/2$ , where $n^d$ represents pixel size in a fixed image window. In the case that magnitude measurements are corrupted by noise, we provide a thresholding scheme with theoretical guarantees for sparsity at most $\mathcal {O}(n^{d\theta })$ for $\theta < 1/4$ that obviates the need for MISTR to explicitly handle noisy autocorrelation data. Detailed and reproducible numerical experiments demonstrate the effectiveness of our algorithm, showing that in practice MISTR enjoys time complexity which is nearly linear in the size of the input. [ABSTRACT FROM AUTHOR]

Time-frequency representation (TFR) plays a significant role in interpreting and analyzing nonstationary multi-mode signals. However, currently, it is still challenging to handle multi-mode signals with closely-spaced or spectrally-overlapped instantaneous frequencies (IFs), especially under low signal-to-noise ratio (SNR) conditions. To address this issue, we propose an enhanced TFR and mode decomposition (ETFR-MD) method, which is especially suitable to represent and decompose multi-mode signals with such complex IFs. The proposed ETFR-MD method exploits both the IFs and instantaneous amplitudes (IAs) of the signal under investigation. First, we design an initial IF estimation method to deal with overlapped IFs. Then, a low-complexity mode enhancement scheme is proposed so that the enhanced IFs could better fit the underlying IF laws. After that, three alternatives, i.e., short-time Fourier transform (STFT) coefficients, de-chirping, and intrinsic chirp component decomposition (ICCD), are considered for IA recovery. Finally, the extracted IAs are combined with the enhanced IFs to reconstruct each signal mode, respectively. To gain more insights, we quantitatively analyze the interference during mode decomposition and derive the optimal window length for mode separation. Experimental results implemented on both simulated and real-world data confirm the superior performance of the ETFR-MD compared with the state-of-the-art solutions. [ABSTRACT FROM AUTHOR]

Graphons are infinite-dimensional objects that represent the limit of convergent sequences of graphs as their number of nodes goes to infinity. This paper derives a theory of graphon signal processing centered on the notions of graphon Fourier transform and linear shift invariant graphon filters, the graphon counterparts of the graph Fourier transform and graph filters. It is shown that for convergent sequences of graphs and associated graph signals: (i) the graph Fourier transform converges to the graphon Fourier transform when the graphon signal is bandlimited; (ii) the spectral and vertex responses of graph filters converge to the spectral and vertex responses of graphon filters with the same coefficients. These theorems imply that for graphs that belong to certain families, i.e., that are part of sequences that converge to a certain graphon, graph Fourier analysis and graph filter design have well defined limits. In turn, these facts extend applicability of graph signal processing to graphs with large number of nodes — since signal processing pipelines designed for limit graphons can be applied to finite graphs — and to dynamic graphs — since we can relate the result of SP pipelines designed for different graphs from the same convergent graph sequence. [ABSTRACT FROM AUTHOR]

Deep convolutional neural networks (DCNNs) have recently emerged as a powerful tool to deliver breakthrough performances in various image analysis and processing applications. However, DCNNs lack a strong theoretical foundation and require massive amounts of training data. More recently, the deep scattering network (DSN), a variant of DCNNs, has been proposed to address these issues. DSNs inherit the hierarchical structure of DCNNs, but replace data-driven linear filters with predefined fixed multi-scale wavelet filters, which facilitate an in-depth understanding of DCNNs and also offer the state-of-the-art performance in image classification. Unfortunately, DSNs suffer from a major drawback: they are suitable for stationary image textures but not non-stationary image textures, since 2D wavelets are intrinsically linear translation-invariant filters in the Fourier transform domain. The objective of this paper is to overcome this drawback using the fractional wavelet transform (FRWT) which can be viewed as a bank of linear translation-variant multi-scale filters and thus may be well suited for non-stationary texture analysis. We first propose the fractional wavelet scattering transform (FRWST) based upon the FRWT. Then, we present a generalized structure for the DSN by cascading fractional wavelet convolutions and modulus operators. Basic properties of this generalized DSN are derived, followed by a fast implementation of the generalized DSN as well as their practical applications. The theoretical derivations are validated via computer simulations. [ABSTRACT FROM AUTHOR]

Set functions are functions (or signals) indexed by the powerset (set of all subsets) of a finite set N. They are fundamental and ubiquitous in many application domains and have been used, for example, to formally describe or quantify loss functions for semantic image segmentation, the informativeness of sensors in sensor networks the utility of sets of items in recommender systems, cooperative games in game theory, or bidders in combinatorial auctions. In particular, the subclass of submodular functions occurs in many optimization and machine learning problems. In this paper, we derive discrete-set signal processing (SP), a novel shift-invariant linear signal processing framework for set functions. Discrete-set SP considers different notions of shift obtained from set union and difference operations. For each shift it provides associated notions of shift-invariant filters, convolution, Fourier transform, and frequency response. We provide intuition for our framework using the concept of generalized coverage function that we define, identify multivariate mutual information as a special case of a discrete-set spectrum, and motivate frequency ordering. Our work brings a new set of tools for analyzing and processing set functions, and, in particular, for dealing with their exponential nature. We show two prototypical applications and experiments: compression in submodular function optimization and sampling for preference elicitation in combinatorial auctions. [ABSTRACT FROM AUTHOR]

The Fourier transform is an important operation in signal processing. However, its exact computation on digital computers can be problematic. In this paper we consider the computability of the Fourier transform and the discrete-time Fourier transform (DTFT). We construct a computable bandlimited absolutely integrable signal that has a continuous Fourier transform, which is, however, not Turing computable. Further, we also construct a computable sequence such that the DTFT is not Turing computable. Turing computability models what is theoretically implementable on a digital computer. Hence, our result shows that the Fourier transform of certain signals cannot be computed on digital hardware of any kind, including CPUs, FPGAs, and DSPs. This also implies that there is no symmetry between the time and frequency domain with respect to computability. Therefore, numerical approaches which employ the frequency domain representation of a signal (like calculating the convolution by performing a multiplication in the frequency domain) can be problematic. Interestingly, an idealized analog machine can compute the Fourier transform. However, it is unclear whether and how this theoretical superiority of the analog machine can be translated into practice. Further, we show that it is not possible to find an algorithm that can always decide for a given signal whether the Fourier transform is computable or not. [ABSTRACT FROM AUTHOR]

We study conditions that allow accurate graphical model selection from non-stationary data. The observed data is modelled as a vector-valued zero-mean Gaussian random process whose samples are uncorrelated but have different covariance matrices. This model contains as special cases the standard setting of i.i.d. samples as well as the case of samples forming a stationary time series. More generally, our approach applies to any data for which efficient decorrelation transforms, such as the Fourier transform for stationary time series, are available. By analyzing a conceptually simple model selection method, we derive a sufficient condition on the required sample size for accurate graphical model selection based on non-stationary data. [ABSTRACT FROM AUTHOR]

The offset linear canonical transform (OLCT) plays an important role in many fields of optics and signal processing. In this paper, we address the problem of signal filtering and reconstruction in the OLCT domain based on new convolution theorems. Firstly, we propose new convolution and product theorems for the OLCT, which state that a modified ordinary convolution in the time domain is equivalent to simple multiplication operations for the OLCT and the Fourier transform (FT). Moreover, it is expressible by a one dimensional integral and is easy to implement in designing filters. The classical convolution theorem in the FT domain is shown to be a special case of our derived results. Then, a practical multichannel sampling expansion for band-limited signal with the OLCT is introduced. This sampling expansion constructed by the new convolution structure can reduce the effect of spectral leakage and is easy to implement. By designing OLCT filters, we can obtain derivative sampling and second-order derivative interpolation. Furthermore, potential applications of the multichannel sampling are discussed. Last, based on the new convolution structure, we investigate and discuss several applications, including swept-frequency filter analysis, image denosing and image encryption. Some illustrations and simulations are presented to verify the validity and effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Frequency-resolved optical gating (FROG) is a popular technique for complete characterization of ultrashort laser pulses. The acquired data in FROG, called FROG trace, is the Fourier magnitude of the product of the unknown pulse with a time-shifted version of itself, for several different shifts. To estimate the pulse from the FROG trace, we propose an algorithm that minimizes a smoothed non-convex least-squares objective function. The method consists of two steps. First, we approximate the pulse by an iterative spectral algorithm. Then, the attained initialization is refined based upon a sequence of block stochastic gradient iterations. The algorithm is theoretically simple, numerically scalable, and easy-to-implement. Empirically, our approach outperforms the state-of-the-art when the FROG trace is incomplete, that is, when only few shifts are recorded. Simulations also suggest that the proposed algorithm exhibits similar computational cost compared to a state-of-the-art technique for both complete and incomplete data. In addition, we prove that in the vicinity of the true solution, the algorithm converges to a critical point. A Matlab implementation is publicly available at https://github.com/samuelpinilla/FROG. [ABSTRACT FROM AUTHOR]

Graph sampling addresses the problem of selecting a node subset in a graph to collect samples, so that a $K$ -bandlimited signal can be reconstructed with high fidelity. Assuming an independent and identically distributed (i.i.d.) noise model, minimizing the expected mean square error (MMSE) leads to the known A-optimality criterion for graph sampling, which is expensive to compute and difficult to optimize. In this paper, we propose an augmented objective based on Neumann series that well approximates the A-optimal criterion and is amenable to greedy optimization. Specifically, we show that a shifted A-optimal criterion can be equivalently written as a function of an ideal low-pass (LP) graph filter, which in turn can be approximated efficiently via fast graph Fourier transform (FGFT). Minimizing the new objective, we select nodes greedily without large matrix inversions using a matrix inverse lemma. Further, for the dynamic subset sampling case where node availability varies across time, we propose an extended sampling strategy that replaces offline samples one-by-one in the selected set. For signal reconstruction, we propose an accompanied biased signal recovery strategy that reuses the approximated filter from sampling. Experiments show that our reconstruction is more robust to large noise than the least squares (LS) solution, and our sampling strategy far outperforms several existing schemes. [ABSTRACT FROM AUTHOR]

Compared with the Fourier analysis, the fractional Fourier analysis is more suitable to process linear frequency modulation type non-stationary functions. To the best of our knowledge, the theoretical framework of the fractional Fourier analysis has not well established yet, especially for the fractional Fourier series (FrFS) and the discrete fractional Fourier transform (DFrFT) algorithms. To tackle with these problems, the efficient FrFS and DFrFT algorithms based on the Möbius function are proposed. First, the existence and applicability of the FrFS are analyzed basing on the Möbius inversion formula. Second, two kinds of fast algorithms for the infinite/finite FrFS are proposed. Then, based on the amplitude scaling relationship between the FrFS and samples of the FrFT, two efficient DFrFT algorithms are obtained, which are noted as the arithmetic discrete fractional Fourier transform (ADFrFT)-I and the ADFrFT-II. Importantly, the multiplication complexity of the two proposed ADFrFT algorithms is reduced to $O(M)$ , which is less than that of the state-of-the-art DFrFT algorithms. The parallel butterfly structure of the ADFrFT-II algorithm is suitable for the very large scale integration implementation. Finally, the simulations justify the efficiency of the ADFrFT algorithms in filtering and parameter evaluation of radar and optical signals. [ABSTRACT FROM AUTHOR]

Convolution sum system representations are commonly used in signal processing. It is known that the convolution sum, treated as the limit of its partial sums, can be divergent for certain continuous signals and stable linear time-invariant (LTI) systems, even when the convergence of the partial sums is treated in a distributional setting. In this paper, we ask a far more general question: is it at all possible to define a generalized convolution sum with natural properties that works for all absolutely integrable continuous signals that vanish at infinity and all stable LTI systems? We prove that the answer is “no.” Further, for certain subspaces, we give a sufficient and necessary condition for uniform convergence. Finally, we discuss the implications of our results on the effectiveness of window functions in the convolution sum. [ABSTRACT FROM AUTHOR]

Graph filters are one of the core tools in graph signal processing. A central aspect of them is their direct distributed implementation. However, the filtering performance is often traded with distributed communication and computational savings. To improve this tradeoff, this paper generalizes state-of-the-art distributed graph filters to filters where every node weights the signal of its neighbors with different values while keeping the aggregation operation linear. This new implementation, labeled as edge-variant graph filter, yields a significant reduction in terms of communication rounds while preserving the approximation accuracy. In addition, we characterize a subset of shift-invariant graph filters that can be described with edge-variant recursions. By using a low-dimensional parameterization, these shift-invariant filters provide new insights in approximating linear graph spectral operators through the succession and composition of local operators, i.e., fixed support matrices. A set of numerical results shows the benefits of the edge-variant graph filters over current methods and illustrates their potential to a wider range of applications than graph filtering. [ABSTRACT FROM AUTHOR]

Linear canonical transforms (LCTs) are of importance in many areas of science and engineering with many applications. Therefore, a satisfactory discrete implementation is of considerable interest. Although there are methods that link the samples of the input signal to the samples of the linear canonical transformed output signal, no widely-accepted definition of the discrete LCT has been established. We introduce a new approach to defining the discrete linear canonical transform (DLCT) by employing operator theory. Operators are abstract entities that can have both continuous and discrete concrete manifestations. Generating the continuous and discrete manifestations of LCTs from the same abstract operator framework allows us to define the continuous and discrete transforms in a structurally analogous manner. By utilizing hyperdifferential operators, we obtain a DLCT matrix, which is totally compatible with the theory of the discrete Fourier transform (DFT) and its dual and circulant structure, which makes further analytical manipulations and progress possible. The proposed DLCT is to the continuous LCT, what the DFT is to the continuous Fourier transform. The DLCT of the signal is obtained simply by multiplying the vector holding the samples of the input signal by the DLCT matrix. [ABSTRACT FROM AUTHOR]

Long time coherent integration (LTCI) technique enhances radar detection of maneuvering weak targets. Unfortunately, range migration (RM) and Doppler frequency migration (DFM) would occur during the integration period. Existing LTCI methods are all based on the assumption that the target is of single motion model (i.e., the target's motion model is fixed) during the long integration time. However, with increasing target's maneuverability and long observation time (needed to detect weak targets), the target's motion model is often changing (i.e., target is of multiple motion models) during the integration time, which would reduce the performance of existing LTCI methods significantly. In this paper, we address the LTCI problem for detecting a maneuvering weak target with multiple motion models, where the target signal model is first established. Thereafter, the short-time generalized Radon Fourier transform (STGRFT) based LTCI algorithm is proposed. The STGRFT method could not only eliminate RM and DFM but also estimate the model-changing point (i.e., the time when target's motion model changes) and accumulate the target energy distributed in different motion stages (corresponding to different motion models). Finally, numerical and real-data experiments are carried out to demonstrate its effectiveness. The results confirm that in terms of integration gain, input–output signal-to-noise ratio performance and detection ability, STGRFT-based method is superior to the existing popular LTCI algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new inference procedure for understanding non-stationary processes, under the framework of evolutionary spectra developed by Priestley. Among various frameworks of modeling non-stationary processes, the distinguishing feature of the evolutionary spectra is its focus on the physical meaning of frequency. The classical estimate of the evolutionary spectral density is based on a double-window technique consisting of a short-time Fourier transform and a smoothing. However, smoothing is known to suffer from the so-called bias leakage problem. By incorporating Thomson's multitaper method that was originally designed for stationary processes, we propose an improved estimate of the evolutionary spectral density, and analyze its bias/variance/resolution tradeoff. As an application of the new estimate, we further propose a non-parametric rank-based stationarity test, and provide various experimental studies. [ABSTRACT FROM AUTHOR]

We study the problem of constructing a graph Fourier transform (GFT) for directed graphs (digraphs), which decomposes graph signals into different modes of variation with respect to the underlying network. Accordingly, to capture low, medium, and high frequencies we seek a digraph (D)GFT such that the orthonormal frequency components are as spread as possible in the graph spectral domain. To that end, we advocate a two-step design whereby we 1) find the maximum directed variation (i.e., a novel notion of frequency on a digraph) a candidate basis vector can attain and 2) minimize a smooth spectral dispersion function over the achievable frequency range to obtain the desired spread DGFT basis. Both steps involve non-convex, orthonormality-constrained optimization problems, which are efficiently tackled via a feasible optimization method on the Stiefel manifold that provably converges to a stationary solution. We also propose a heuristic to construct the DGFT basis from Laplacian eigenvectors of an undirected version of the digraph. We show that the spectral-dispersion minimization problem can be cast as supermodular optimization over the set of candidate frequency components, whose orthonormality can be enforced via a matroid basis constraint. This motivates adopting a scalable greedy algorithm to obtain an approximate solution with quantifiable worst-case spectral dispersion. We illustrate the effectiveness of our DGFT algorithms through numerical tests on synthetic and real-world networks. We also carry out a graph-signal denoising task, whereby the DGFT basis is used to decompose and then low pass filter temperatures recorded across the United States. [ABSTRACT FROM AUTHOR]

The rise of graph-structured data such as social networks, regulatory networks, citation graphs, and functional brain networks, in combination with resounding success of deep learning in various applications, has brought the interest in generalizing deep learning models to non-Euclidean domains. In this paper, we introduce a new spectral domain convolutional architecture for deep learning on graphs. The core ingredient of our model is a new class of parametric rational complex functions (Cayley polynomials) allowing to efficiently compute spectral filters on graphs that specialize on frequency bands of interest. Our model generates rich spectral filters that are localized in space, scales linearly with the size of the input data for sparsely connected graphs, and can handle different constructions of Laplacian operators. Extensive experimental results show the superior performance of our approach, in comparison to other spectral domain convolutional architectures, on spectral image classification, community detection, vertex classification, and matrix completion tasks. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the retrieval of the modes of multicomponent signals from their downsampled short-time Fourier transform. To this end, we first recall signal reconstruction techniques based on shifted downsampled short-time Fourier transform, and then explain how to adapt these to the context of the retrieval of the modes of a multicomponent signal. We then show, on simulated and real data, that downsampling the short-time Fourier transform does not result in a significant performance loss of the mode retrieval procedures. Finally, comparisons with recent mode retrieval techniques based on synchrosqueezing transform are carried out, the focus being put on the amount of information needed to perform the recovery of the modes. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel generalization of the graph Fourier transform (GFT). Our approach is based on separately considering the definitions of signal energy and signal variation, leading to several possible orthonormal GFTs. Our approach includes traditional definitions of the GFT as special cases, while also leading to new GFT designs that are better at taking into account the irregular nature of the graph. As an illustration, in the context of sensor networks we use the Voronoi cell area of vertices in our GFT definition, showing that it leads to a more sensible definition of graph signal energy even when sampling is highly irregular. [ABSTRACT FROM AUTHOR]

Nonnegative matrix factorization (NMF) and nonnegative tensor factorization (NTF) are important tools for modeling nonnegative data, which gained increasing popularity in various fields, a significant one of which is audio processing. However, there are still many problems in audio processing, for which the NMF (or NTF) model has not been successfully utilized. In this paper, we propose a new algorithm based on the NMF (and NTF) in the short-time Fourier domain for solving a large class of audio inverse problems with missing or corrupted time-domain samples. The proposed approach overcomes the difficulty of employing a model in the frequency domain to recover time-domain samples with the help of probabilistic modeling. Its performance is demonstrated for the following applications: audio declipping and declicking (never solved with NMF/NTF modeling prior to this paper); joint audio declipping/declicking and source separation (never solved with NMF/NTF modeling or any other method prior to this paper); and compressive sampling recovery and compressive sampling-based informed source separation (an extremely low complexity encoding scheme that is possible with the proposed approach and has never been proposed prior to this paper). [ABSTRACT FROM AUTHOR]

This paper is a contribution to the old problem of representing a signal in the coordinates of time and frequency. We review the fundamental Hilbert transform relationship in systems analysis and argue that the dual relationship assumed in signal analysis, i.e. spectral single-sidedness is not necessarily justifiable. Therefore, we abandon the analytic signal and utilize a carefully parameterized signal model composed of a superposition of complex, AM–FM components that enables rigorous definition of instantaneous amplitude and instantaneous frequency. We then propose the instantaneous spectrum (IS) and prove that it exactly localizes signal components in an instantaneous bandwidth sense. The relation of the IS to traditional time-frequency distributions is discussed and comparative examples are provided. It is shown that under certain conditions the IS specializes to the Fourier spectrum and properties of the IS, similar to standard Fourier transform properties, are given. [ABSTRACT FROM AUTHOR]

Symbol timing offset (STO) estimation constitutes an important part in orthogonal frequency-division multiplexing (OFDM) signal synchronization, and many blind methods based on the maximum likelihood (ML) principle have been proposed. A theoretical analysis of the estimation performance, however, is very difficult, due in part to the discrete nature of the STO. As a result, most studies on OFDM STO estimation have relied only on computer simulation for performance evaluation. This paper presents a theoretical performance analysis for ML-based blind OFDM STO estimation. We start with a review of the formulation of ML blind STO estimation problem and its solution. We then conduct the said performance analysis. The analysis turns out to involve a study of the eigenvalues of some matrix functions of the autocorrelation of the received signal. As the general case leads to highly complicated mathematics, we treat the case of full-band OFDM in additive white Gaussian noise in more detail. In this case, we are able to obtain mathematically tractable bounds and approximation to the estimation error probability and the corresponding mean-square error. In high signal-to-noise ratio (SNR), these bounds and approximation show inverse power-law dependence on the SNR. We also compare the bounds with simulation results and with an existing approximation in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we study the validity of the usual convolution sum sampling representation of linear time-invariant (LTI) systems. We consider continuous input signals with finite energy that are absolutely integrable and vanish at infinity. Even for these benign signals, the convolution sum does not always converge. There exist LTI systems and signals such that the convolution sum diverges even in a distributional sense. This result shows that the practice of multiplying a signal with a Dirac comb and convolving subsequently with the impulse response of the LTI system is not valid for this signal space. We further fully characterize the LTI systems for which we have convergence for all signals in the space, and establish a connection between the pointwise, uniform, and distributional convergence. In particular, we show that the convolution sum converges in a distributional sense if and only it converges in a classical pointwise sense. Hence, for this signal space, nothing can be gained by treating the convergence in a distributional sense. [ABSTRACT FROM AUTHOR]

Finding a balance between observation duration and detection rates is the ultimate goal of the detection of ultrahigh speed targets. However, short observation durations, both across range unit, and Doppler frequency migration, may severely limit the detection performance of ultrahigh speed targets. Although, traditional coherent integration methods can efficiently accumulate signal energy to produce a high signal-to-noise-ratio measurement, they often need to search for unknown motion parameters. This search is time consuming and unacceptable for the real-time detection of ultrahigh speed targets. In this paper, a coherent-like detection method is designed based on the finite-dimension theory of Wigner matrices along with velocity identification. The proposed method can efficiently integrate signal energy without rendering motion parameters. We use the distribution and mean of the eigenvalues of the constructed matrix, i.e., an additive Wigner matrix, to identify velocities and detect ultrahigh speed targets, respectively. Simulation results validate the theoretical derivation, superiority and operability of the proposed method. [ABSTRACT FROM AUTHOR]

A complete framework for the linear time-invariant (LTI) filtering theory of bivariate signals is proposed based on tailored quaternion Fourier transform. This framework features a direct description of LTI filters in terms of their eigenproperties enabling compact calculus and physically interpretable filtering relations in the frequency domain. The design of filters exhibiting fundamental properties of polarization optics (birefringence and diattenuation) is straightforward. It yields an efficient spectral synthesis method and new insights on Wiener filtering for bivariate signals with prescribed frequency-dependent polarization properties. This generic framework facilitates original descriptions of bivariate signals in two components with specific geometric or statistical properties. Numerical experiments support our theoretical analysis and illustrate the relevance of the approach on synthetic data. [ABSTRACT FROM AUTHOR]

We examine Fourier transforms of real-valued stationary time series from the point of view of the statistical propriety. Processes with a large dynamic range spectrum have transforms that are very significantly improper for some frequencies; the real and imaginary parts can be highly correlated, and the periodogram will not have the standard chi-square distribution at these frequencies, nor have two degrees of freedom. Use of a taper reduces impropriety to just frequencies close to zero and Nyquist only, and frequency ranges where the propriety breaks down can be quite accurately and easily predicted by half the autocorrelation width of $|H*H(2f)|,$ denoted by $c,$ where $H(f)$ is the Fourier transform of the taper and $*$ denotes convolution. For vector time series we derive an improved distributional approximation for minus twice the log of the generalized likelihood ratio test statistic for testing for propriety of the Fourier transform at any frequency, and compare frequency range cutoffs for propriety determined by the hypothesis test with those determined by $c.$ [ABSTRACT FROM AUTHOR]

Slepian functions provide a solution to the optimization problem of joint time-frequency localization. Here, this concept is extended by using a generalized optimization criterion that favors energy concentration in one interval while penalizing energy in another interval, leading to the “augmented” Slepian functions. Mathematical foundations together with examples are presented in order to illustrate the most interesting properties that these generalized Slepian functions show. Also the relevance of this novel energy-concentration criterion is discussed along with some of its applications. [ABSTRACT FROM AUTHOR]

By using the manifold separation technique (MST), we develop a computationally efficient yet accurate estimator for localization of multiple incoherently distributed (ID) sources. In this paper, we have made the following main contributions: first, we use the MST to derive a closed-form expression for the ID signal covariance matrix that is applicable to the case with arbitrary array geometries or large angular spreads; second, we find that the two-dimensional spatial spectrum can be computed efficiently by using the discrete Fourier transform algorithms coupled with the unweighted (or Gaussian-weighted) moving average for the uniformly (or Gaussian) distributed ID sources; finally, we employ the first-order Taylor expansion to formulate a weighted least-squares approach that can improve the estimation performance significantly. Numerical results demonstrate that with less complexity, the proposed estimator offers better estimation performance compared with several classical estimators. [ABSTRACT FROM AUTHOR]

We propose a novel soft-input soft-output equalizer for single-carrier transmissions over unknown frequency-selective block-fading channels. Our equalizer leverages the recently proposed parametric bilinear generalized approximate message passing algorithm for joint channel-estimation and symbol-detection, and exploits fast Fourier transform (FFT)-processing to achieve a per-symbol complexity that grows only logarithmically in the channel delay-spread. Furthermore, it supports the use of Gaussian mixture models to support the approximately sparse nature of wideband wireless channel responses. Numerical experiments, conducted using physically motivated Saleh–Valenzuela channel models, show that the proposed approach achieves channel normalized mean square error and bit error rate that are significant improved over existing turbo frequency-domain equalization approaches for unknown channels. Additional experiments show that the proposed scheme facilitates much higher spectral efficiencies than sparse deconvolution methods based on convex relaxation. [ABSTRACT FROM AUTHOR]

We consider in this paper how to encode a finite-energy random field via a finite number of bits. We present a method giving rise to a finite-bit representation for a given field. We analyze the overall reconstruction error associated with this method, and see that it is a summation which consists of the error coming from the sampling and quantization domains. Then, we search for the best sampling and quantization parameters to get the optimal reconstruction error for a given number of bits. This optimization leads to the number of bits versus reconstruction error curve consisting of best achievable points, which is reminiscent of rate distortion curve in information theory. [ABSTRACT FROM AUTHOR]

We present a novel diffusion scheme for online kernelbased learning over networks. So far, a major drawback of any online learning algorithm, operating in a reproducing kernel Hilbert space (RKHS), is the need for updating a growing number of parameters as time iterations evolve. Besides complexity, this leads to an increased need of communication resources in a distributed setting. In contrast, we propose to approximate the solution as a fixed-size vector (of larger dimension than the input space) using the previously introduced framework of random Fourier features. This paves the way to use standard linear combine-then-adapt techniques. To the best of our knowledge, this is the first time that a complete protocol for distributed online learning in RKHS is presented. Conditions for asymptotic convergence and boundness of the networkwise regret are also provided. The simulated tests illustrate the performance of the proposed scheme. [ABSTRACT FROM AUTHOR]

Alternating minimization, or Fienup methods, have a long history in phase retrieval. We provide new insights related to the empirical and theoretical analysis of these algorithms when used with Fourier measurements and combined with convex priors. In particular, we show that Fienup methods can be viewed as performing alternating minimization on a regularized nonconvex least-squares problem with respect to amplitude measurements. Furthermore, we prove that under mild additional structural assumptions on the prior (semialgebraicity), the sequence of signal estimates has a smooth convergent behavior toward a critical point of the nonconvex regularized least-squares objective. Finally, we propose an extension to Fienup techniques, based on a projected gradient descent interpretation and acceleration using inertial terms. We demonstrate experimentally that this modification combined with an l1 prior constitutes a competitive approach for sparse phase retrieval. [ABSTRACT FROM AUTHOR]

An emerging way to deal with high-dimensional noneuclidean data is to assume that the underlying structure can be captured by a graph. Recently, ideas have begun to emerge related to the analysis of time-varying graph signals. This paper aims to elevate the notion of joint harmonic analysis to a full-fledged framework denoted as time-vertex signal processing, that links together the time-domain signal processing techniques with the new tools of graph signal processing. This entails three main contributions: a) We provide a formal motivation for harmonic time-vertex analysis as an analysis tool for the state evolution of simple partial differential equations on graphs; b) we improve the accuracy of joint filtering operators by up-to two orders of magnitude; c) using our joint filters, we construct time-vertex dictionaries analyzing the different scales and the local time-frequency content of a signal. The utility of our tools is illustrated in numerous applications and datasets, such as dynamic mesh denoising and classification, still-video inpainting, and source localization in seismic events. Our results suggest that joint analysis of time-vertex signals can bring benefits to regression and learning. [ABSTRACT FROM AUTHOR]

Singular spectrum analysis (SSA) is a signal decomposition technique that aims at expanding signals into interpretable and physically meaningful components (e.g., sinusoids, noise, etc.). This paper presents new theoretical and practical results about the separability of the SSA and introduces a new method called sliding SSA. First, the SSA is combined with an unsupervised classification algorithm to provide a fully automatic data-driven component extraction method for which we investigate the limitations for components separation in a theoretical study. Second, the detailed automatic SSA method is used to design an approach based on a sliding analysis window, which provides better results than the classical SSA method when analyzing nonstationary signals with a time-varying number of components. Finally, the proposed sliding SSA method is compared to the empirical mode decomposition and to the synchrosqueezed short-time Fourier transform, applied on both synthetic and real-world signals. [ABSTRACT FROM AUTHOR]

This paper presents an extension of the integrated time-chirp rate analysis technique, known as the parameterized centroid frequency-chirp rate distribution (PCFCRD), for noisy multicomponent linear frequency modulated signals analysis. The PCFCRD is based on a newly defined correlation function and its auto term accumulation is two-dimensionally coherent. The principle, cross term characteristic, implementation, properties, parameter selection criterion, antinoise performance, and estimation accuracy are analyzed for the PCFCRD. In this paper, comparisons with the coherently integrated cubic phase function, maximum likelihood method, and Lv's distribution are performed. With mathematic analyses and numerical simulations, we demonstrate that the PCFCRD outperforms these three representative counterparts. Further, by combining with analyses of the PCFCRD, several unclear mechanisms of the constant delay introduction are mathematically interpreted, especially quantitative influences on the chirp rate resolution and theoretical antinoise performance. [ABSTRACT FROM AUTHOR]

A novel approach toward the spectral analysis of stationary random bivariate signals is proposed. Unlike existing approaches, the proposed framework exhibits a natural link between well-defined statistical objects and physical parameters for bivariate signals. Using the quaternion Fourier transform, we introduce a quaternion-valued spectral representation of random bivariate signals seen as complex-valued sequences. This makes possible the definition of a scalar quaternion-valued spectral density and the corresponding autocovariance for bivariate signals. This spectral density can be meaningfully interpreted in terms of frequency-dependent polarization attributes. A natural decomposition of the spectral density of any random bivariate signal in terms of unpolarized and polarized components is introduced. Nonparametric spectral density estimation is investigated, and we introduce the polarization periodogram of a random bivariate signal. Numerical experiments support our theoretical analysis, illustrating the relevance of the approach on synthetic data. [ABSTRACT FROM PUBLISHER]

Variational mode decomposition (VMD), a recently introduced method for adaptive data analysis, has aroused much attention in various fields. However, the VMD is formulated based on the assumption of narrow-band property of the signal model. To analyze wide-band nonlinear chirp signals (NCSs), we present an alternative method called variational nonlinear chirp mode decomposition (VNCMD). The VNCMD is developed from the fact that a wideband NCS can be transformed to a narrow-band signal by using demodulation techniques. Our decomposition problem is, thus, formulated as an optimal demodulation problem, which is efficiently solved by the alternating direction method of multipliers. Our method can be viewed as a time–frequency filter bank, which concurrently extracts all the signal modes. Some simulated and real data examples are provided showing the effectiveness of the VNCMD in analyzing NCSs containing close or even crossed modes. [ABSTRACT FROM PUBLISHER]

Analysis of signals defined over graphs has been of interest in the recent years. In this regard, many concepts from the classical signal processing theory have been extended to the graph case, including uncertainty principles that study the concentration of a signal on a graph and in its graph Fourier basis (GFB). This paper advances a new way to formulate the uncertainty principle for signals defined over graphs, by using a nonlocal measure based on the notion of sparsity. To be specific, the total number of nonzero elements of a graph signal and its corresponding graph Fourier transform (GFT) is considered. A theoretical lower bound for this total number is derived, and it is shown that a nonzero graph signal and its GFT cannot be arbitrarily sparse simultaneously. When the graph has repeated eigenvalues, the GFB is not unique. Since the derived lower bound depends on the selected GFB, a method that constructs a GFB with the minimal uncertainty bound is provided. In order to find signals that achieve the derived lower bound (i.e., the most compact on the graph and in the GFB), sparse eigenvectors of the graph are investigated. It is shown that a connected graph has a 2-sparse eigenvector (of the graph Laplacian) when there exist two nodes with the same neighbors. In this case, the uncertainty bound is very low, tight, and independent of the global structure of the graph. For several examples of classical and real-world graphs, it is shown that 2-sparse eigenvectors, in fact, exist. [ABSTRACT FROM PUBLISHER]

As a generalization of the ordinary wavelet transform, the fractional wavelet transform (FRWT) is a very promising tool for signal analysis and processing. Many of its fundamental properties are already known; however, little attention has been paid to its sampling theory. In this paper, we first introduce the concept of multiresolution analysis associated with the FRWT, and then propose a sampling theorem for signals in FRWT-based multiresolution subspaces. The necessary and sufficient condition for the sampling theorem is derived. Moreover, sampling errors due to truncation and aliasing are discussed. The validity of the theoretical derivations is demonstrated via simulations. [ABSTRACT FROM PUBLISHER]

A mathematical framework for similarity recovery from threshold-based sampling based on the concept of quasi-isometry is introduced. The approach leads to a unified model of threshold-based sampling schemes which comprises “send-on-delta” (SOD), “leaky integrate-and-fire” or the psychophysical Weber–Fechner law as examples and gives raise to novel sampling schemes such as “Leaky SOD.” As a result, the input and the output spaces become metric spaces being linked by lower and upper bounds under general conditions which go beyond assumptions in the signal recovery context. In particular, the proposed approach allows us to estimate the signal reconstruction error by resampling the reconstructed signal and applying the quasi-isometric distance measure in the sample space. [ABSTRACT FROM PUBLISHER]

Given a dataset, the task of learning a transform that allows sparse representations of the data bears the name of dictionary learning. In many applications, these learned dictionaries represent the data much better than the static well-known transforms (Fourier, Hadamard etc.). The main downside of learned transforms is that they lack structure and, therefore, they are not computationally efficient, unlike their classical counterparts. These posse several difficulties especially when using power limited hardware such as mobile devices, therefore, discouraging the application of sparsity techniques in such scenarios. In this paper, we construct orthogonal and nonorthogonal dictionaries that are factorized as a product of a few basic transformations. In the orthogonal case, we solve exactly the dictionary update problem for one basic transformation, which can be viewed as a generalized Givens rotation, and then propose to construct orthogonal dictionaries that are a product of these transformations, guaranteeing their fast manipulation. We also propose a method to construct fast square but nonorthogonal dictionaries that are factorized as a product of few transforms that can be viewed as a further generalization of Givens rotations to the nonorthogonal setting. We show how the proposed transforms can balance very well data representation performance and computational complexity. We also compare with classical fast and learned general and orthogonal transforms. [ABSTRACT FROM PUBLISHER]

The aim of this paper is to propose distributed strategies for adaptive learning of signals defined over graphs. Assuming the graph signal to be bandlimited, the method enables distributed reconstruction, with guaranteed performance in terms of mean-square error, and tracking from a limited number of sampled observations taken from a subset of vertices. A detailed mean-square analysis is carried out and illustrates the role played by the sampling strategy on the performance of the proposed method. Finally, some useful strategies for distributed selection of the sampling set are provided. Several numerical results validate our theoretical findings, and illustrate the performance of the proposed method for distributed adaptive learning of signals defined over graphs. [ABSTRACT FROM PUBLISHER]

Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deterministic setting, ignoring the impact of stochasticity in both the graph topology and the signal itself. To bridge this gap, we examine the statistical behavior of the two key filter types, finite impulse response and autoregressive moving average graph filters, when operating on random time-varying graph signals (or random graph processes) over random time-varying graphs. Our analysis shows that 1) in expectation, the filters behave as the same deterministic filters operating on a deterministic graph, being the expected graph, having as input signal a deterministic signal, being the expected signal, and 2) there are meaningful upper bounds for the variance of the filter output. We conclude this paper by proposing two novel ways of exploiting randomness to improve (joint graph-time) noise cancellation, as well as to reduce the computational complexity of graph filtering. As demonstrated by numerical results, these methods outperform the disjoint average and denoise algorithm and yield a (up to) four times complexity reduction, with a very little difference from the optimal solution. [ABSTRACT FROM PUBLISHER]

Graphs are a central tool in machine learning and information processing as they allow to conveniently capture the structure of complex datasets. In this context, it is of high importance to develop flexible models of signals defined over graphs or networks. In this paper, we generalize the traditional concept of wide sense stationarity to signals defined over the vertices of arbitrary weighted undirected graphs. We show that stationarity is expressed through the graph localization operator reminiscent of translation. We prove that stationary graph signals are characterized by a well-defined power spectral density that can be efficiently estimated even for large graphs. We leverage this new concept to derive Wiener-type estimation procedures of noisy and partially observed signals and illustrate the performance of this new model for denoising and regression. [ABSTRACT FROM PUBLISHER]

This paper puts forward a generalization of the short-time Fourier-based synchrosqueezing transform using a new local estimate of instantaneous frequency. Such a technique enables not only to achieve a highly concentrated time-frequency representation for a wide variety of amplitude- and frequency-modulated multicomponent signals but also to reconstruct their modes with a high accuracy. Numerical investigation on synthetic and gravitational-wave signals shows the efficiency of this new approach. [ABSTRACT FROM PUBLISHER]