The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
B. Boashash - One of the best experts on this subject based on the ideXlab platform.
-
an improved design of high resolution Quadratic Time frequency distributions for the analysis of nonstationary multicomponent signals using directional compact kernels
IEEE Transactions on Signal Processing, 2017Co-Authors: B. Boashash, Samir OuelhaAbstract:This paper presents a new advanced methodology for designing high resolution Time–frequency distributions (TFDs) of multicomponent nonstationary signals that can be approximated using piece-wise linear frequency modulated (PW-LFM) signals. Most previous kernel design methods assumed that signals auto-terms are mostly centered around the origin of the $(\nu,\tau)$ ambiguity domain while signal cross-terms are mostly away from the origin. This study uses a multicomponent test signal for which each component is modeled as a PW-LFM signal; it finds that the above assumption is a very rough approximation of the location of the auto-terms energy and cross-terms energy in the ambiguity domain and it is only valid for signals that are well separated in the $(t,f)$ domain. A refined investigation led to improved specifications for separating cross-terms from auto-terms in the $(\nu,\tau)$ ambiguity domain. The resulting approach first represents the signal in the ambiguity domain, and then applies a multidirectional signal dependent compact kernel that accounts for the direction of the auto-terms energy. The resulting multidirectional distribution (MDD) approach proves to be more effective than classical methods like extended modified B distribution, S-method, or compact kernel distribution in terms of auto-terms resolution and cross-terms suppression. Results on simulated and real data validate the improved performance of the MDD, showing up to 8% gain as compared to more standard state-of-the-art TFDs.
-
human gait recognition with cane assistive device using Quadratic Time frequency distributions
Iet Radar Sonar and Navigation, 2015Co-Authors: Moeness G Amin, Yimin Zhang, Fauzia Ahmad, B. BoashashAbstract:In this study, the authors consider the problem of human gait recognition in the presence of a walking cane using radars. Quadratic Time-frequency distributions are used to provide the local signal behaviour over frequency and to detail the changes in the Doppler and micro-Doppler signatures over Time. New features that capture the intrinsic differences in the Time-frequency signatures of the gait observed with and without the use of a cane are proposed. The results based on real data experiments conducted in a laboratory environment are provided that validate the effectiveness of the proposed features in discriminating gait with cane from normal human gait.
-
improved discrete definition of Quadratic Time frequency distributions
IEEE Transactions on Signal Processing, 2010Co-Authors: John M Otoole, M Mesbah, B. BoashashAbstract:Computation of a Time-frequency distribution (TFD) requires a discrete version of the continuous distribution. This discrete TFD (DTFD) should be free from aliasing and conserve all the important mathematical properties of the continuous distribution. Existing DTFD definitions, however, poorly approximate this ideal. One popular definition, the generalized DTFD (GDTFD), is alias free but does not retain all the desirable properties from the continuous distribution. Another definition, the so-called alias-free GDTFD (AF-GDTFD), retains most properties yet is not always alias free. We propose a new DTFD definition, based on the GDTFD, that retains all desirable properties and is always alias free.
-
Resolution measure criteria for the objective assessment of the performance of Quadratic Time-frequency distributions
IEEE Transactions on Signal Processing, 2003Co-Authors: B. Boashash, Viktor SucicAbstract:This paper presents the essential elements for developing objective methods of assessment of the performance of Time-frequency signal analysis techniques. We define a measure for assessing the resolution performance of Time-frequency distributions (TFDs) in separating closely spaced components in the Time-frequency domain. The measure takes into account key attributes of TFDs, such as components mainlobes and sidelobes and cross-terms. The introduction of this measure allows to quantify the quality of TFDs instead of relying solely on visual inspection of their plots. The method of assessment of performance of TFDs also allows the improvement of methodologies for designing high-resolution Quadratic TFDs for Time-frequency analysis of multicomponent signals. Different TFDs, including the modified B distribution, are optimized using this methodology. Examples of a performance comparison of Quadratic TFDs in resolving closely spaced components in the Time-frequency domain, using the proposed resolution measure, are provided.
-
Adaptive instantaneous frequency estimation of multicomponent FM signals using Quadratic Time-frequency distributions
IEEE Transactions on Signal Processing, 2002Co-Authors: Zahir M. Hussain, B. BoashashAbstract:An adaptive approach to the estimation of the instantaneous frequency (IF) of nonstationary mono- and multicomponent FM signals with additive Gaussian noise is presented. The IF estimation is based on the fact that Quadratic Time-frequency distributions (TFDs) have maxima around the IF law of the signal. It is shown that the bias and variance of the IF estimate are functions of the lag window length. If there is a bias-variance tradeoff, then the optimal window length for this tradeoff depends on the unknown IF law. Hence, an adaptive algorithm with a Time-varying and data-driven window length is needed. The adaptive algorithm can utilize any Quadratic TFD that satisfies the following three conditions: First, the IF estimation variance given by the chosen distribution should be a continuously decreasing function of the window length, whereas the bias should be continuously increasing so that the algorithm will converge at the optimal window length for the bias-variance tradeoff, second, the Time-lag kernel filter of the chosen distribution should not perform narrowband filtering in the lag direction in order to not interfere with the adaptive window in that direction; third, the distribution should perform effective cross-terms reduction while keeping high resolution in order to be efficient for multicomponent signals. A Quadratic distribution with high resolution, effective cross-terms reduction and no lag filtering is proposed. The algorithm estimates multiple IF laws by using a tracking algorithm for the signal components and utilizing the property that the proposed distribution enables nonparametric component amplitude estimation. An extension of the proposed TFD consisting of the use of Time-only kernels for adaptive IF estimation is also proposed.
Michael Saks - One of the best experts on this subject based on the ideXlab platform.
-
approximating edit distance within constant factor in truly sub Quadratic Time
arXiv: Data Structures and Algorithms, 2018Co-Authors: Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucky, Michael SaksAbstract:Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in Quadratic Time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear Time algorithm that approximates edit distance within an approximation factor $\text{poly}(\log n)$. In this paper, we provide an algorithm with running Time $\tilde{O}(n^{2-2/7})$ that approximates the edit distance within a constant factor.
-
approximating edit distance within constant factor in truly sub Quadratic Time
Foundations of Computer Science, 2018Co-Authors: Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucky, Michael SaksAbstract:Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in Quadratic Time. Andoni, Krauthgamer and Onak (2010) gave a nearly linear Time algorithm that approximates edit distance within approximation factor poly(log n). In this paper, we provide an algorithm with running Time O(n^2-2/7) that approximates the edit distance within a constant factor.
Ljubisa Stankovic - One of the best experts on this subject based on the ideXlab platform.
-
Time frequency signal analysis with applications
2013Co-Authors: Ljubisa Stankovic, Milos Dakovic, Thayannathan ThayaparanAbstract:Introduction to Fourier Analysis Linear Time-Frequency Representations Quadratic Time-Frequency Distributions Higher Order Time-Frequency Representations Analysis of Non-Stationary Noisy Signals Some Applications of Time-Frequency Analysis.
-
performance of Quadratic Time frequency distributions as instantaneous frequency estimators
IEEE Transactions on Signal Processing, 2003Co-Authors: Veselin N Ivanovic, Milos Dakovic, Ljubisa StankovicAbstract:General performance analysis of the shift covariant class of Quadratic Time-frequency distributions (TFDs) as instantaneous frequency (IF) estimators, for an arbitrary frequency-modulated (FM) signal, is presented. Expressions for the estimation bias and variance are derived. This class of distributions behaves as an unbiased estimator in the case of monocomponent signals with a linear IF. However, when the IF is not a linear function of Time, then the estimate is biased. Cases of white stationary and white nonstationary additive noises are considered. The well-known results for the Wigner distribution (WD) and linear FM signal, and the spectrogram of signals whose IF may be considered as a constant within the lag window, are presented as special cases. In addition, we have derived the variance expression for the spectrogram of a linear FM signal that is quite simple but highly signal dependent. This signal is considered in the cases of other commonly used distributions, such as the Born-Jordan and the Choi-Williams distributions. It has been shown that the reduced interference distributions outperform the WD but only in the case when the IF is constant or its variations are small. Analysis is extended to the IF estimation of signal components in the case of multicomponent signals. All theoretical results are statistically confirmed.
Franz Hlawatsch - One of the best experts on this subject based on the ideXlab platform.
-
wigner distributions nearly everywhere Time frequency analysis of signals systems random processes signal spaces and frames
Signal Processing, 2003Co-Authors: Gerald Matz, Franz HlawatschAbstract:The Wigner distribution (WD) is perhaps the most prominent Quadratic Time-frequency signal representation. In this paper, which has mainly tutorial character but also contains some new results, we describe extensions of the WD concept to multidimensional vector signals, nonstationary random processes, linear Time-varying systems (deterministic and random), linear signal spaces, and frames. We discuss the interpretation and properties of these WD extensions and various relations connecting them. Some application examples are also provided.
-
the hyperbolic class of Quadratic Time frequency representations i constant q warping the hyperbolic paradigm properties and members
IEEE Transactions on Signal Processing, 1993Co-Authors: A Papandreou, Franz Hlawatsch, G F BoudreauxbartelsAbstract:The Time-frequency (TF) version of the wavelet transform and the "affine" Quadratic/bilinear TF representations can be used for a TF analysis with constant-Q characteristic. The paper considers a new approach to constant-Q TF analysis. A specific TF warping transform is applied to Cohen's class of Quadratic TF representations, which results in a new class of Quadratic TF representations with constant-Q characteristic. The new class is related to a "hyperbolic TF geometry" and is thus called the hyperbolic class (HC). Two prominent TF representations previously considered in the literature, the Bertrand P/sub 0/ distribution and the Altes-Marinovic Q-distribution, are members of the new HC. The authors show that any hyperbolic TF representation is related to both the wideband ambiguity function and a "hyperbolic ambiguity function". It is also shown that the HC is the class of all Quadratic TF representations which are invariant to "hyperbolic Time-shifts" and TF scalings, operations which are important in the analysis of Doppler-invariant signals and self-similar random processes. The paper discusses the definition of the HC via constant-Q warping, some signal-theoretic fundamentals of the "hyperbolic TF geometry", and the description of the HC by 2D kernel functions. Several members of the HC are considered, and a list of desirable properties of hyperbolic TF representations is given together with the associated kernel constraints. >
-
linear and Quadratic Time frequency signal representations
IEEE Signal Processing Magazine, 1992Co-Authors: Franz Hlawatsch, G F BoudreauxbartelsAbstract:A tutorial review of both linear and Quadratic representations is given. The linear representations discussed are the short-Time Fourier transform and the wavelet transform. The discussion of Quadratic representations concentrates on the Wigner distribution, the ambiguity function, smoothed versions of the Wigner distribution, and various classes of Quadratic Time-frequency representations. Examples of the application of these representations to typical problems encountered in Time-varying signal processing are provided. >
Robin Thomas - One of the best experts on this subject based on the ideXlab platform.
-
three coloring triangle free graphs on surfaces vii a linear Time algorithm
arXiv: Discrete Mathematics, 2016Co-Authors: Zdenek Dvorak, Daniel Kral, Robin ThomasAbstract:We give a linear-Time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a Quadratic-Time algorithm to output a 3-coloring in the affirmative case. The algorithms also allow to prescribe the coloring for a bounded number of vertices.
-
three coloring triangle free planar graphs in linear Time
Symposium on Discrete Algorithms, 2009Co-Authors: Zdeněk Dvořak, Ken-ichi Kawarabayashi, Robin ThomasAbstract:Grotzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into Quadratic-Time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear Time (Kowalik used a nontrivial data structure to construct an O(n log n) algorithm). We design a linear-Time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product we give a yet simpler proof of Grotzsch's theorem.
