A Signal-Dependent Time-Frequency Representation: Fast Algorithm for Optimal Kernel Design

Abstract

A time-frequency representation based on an optimal, signal-dependent kernel has been proposed recetnly in an attempte to overcome one of the primary limitations of bilinear time-frequency distributions: that the best kernel and distribution depend on the signal to be analyzed. The optimization formulation for the signal-dependent kernel results in a linear program with a unique feature: a tree structure that summarizes a set of constraints on the kernel. In this paper, we present a fast algorithm based on sorting to solve a special class of linear programs that includes the problem of interest. For a kernel with Q variables, the running time of the algorithm is <i>0</i>(<i>Q</i>log<i>Q</i>), which is several orders of magniutde less than any other know method for solving this class of linear programs. This efficiency enables the computation of the signal-dependent, optimal-kernel time-frequency representations at a cost that is on the same order as a fix-dernel distribution. An important property of the optimal kernel is that it takes on essentially only the values of 1 and 0.