Dynamic time warping (DTW) has been applied to a wide range of machine learning problems involving the comparison of time series. An important feature of such time series is that they can sometimes be sparse in the sense that the data takes zero value at many epochs. This corresponds for example to quiet periods in speech or to a lack of physical activity. However, employing conventional DTW for such sparse time series runs a full search ignoring the zero data. Sparse dynamic time warping (SDTW) was previously developed which yields the exact DTW solution while reducing the time complexity by the order of a suitably defined sparsity ratio.This paper focuses on the development and analysis of a fast approximate algorithm for dynamic time warping based on the SDTW framework. We call this fast sparse dynamic time warping (FSDTW). This study includes numerical experiments which compare the performance and complexity of FSDTW with DTW, SDTW and other algorithms that approximate DTW for sparse time series. It is shown that FSDTW reduces the time complexity relative to SDTW by the order of the sparsity ratio with negligible error relative to the exact DTW distance.

Dynamic time warping (DTW) has been applied to a wide range of machine learning problems involving the comparison of time series. An important feature of such time series is that they can sometimes be sparse in the sense that the data takes zero value at many epochs. This corresponds for example to quiet periods in speech or to a lack of physical activity. However, employing conventional DTW for such sparse time series runs a full search ignoring the zero data. So a fast dynamic time warping algorithm that is exactly equivalent to DTW was developed for the unconstrained case where there is no global constraint on the permissible warping path. It was called sparse dynamic time warping (SDTW). In this paper we focus on the development and analysis of a fast dynamic time warping algorithm for the constrained case where there is a global constraint on the permissible warping path, specifically limit the width along the diagonal of the permissible path domain. We call this constrained sparse dynamic time warping (CSDTW). A careful formulation and analysis are performed to determine exactly how CSDTW should treat the zero data. It is shown that CSDTW reduces the computational complexity relative to constrained DTW by about three times the sparsity ratio, which is defined as the arithmetic mean of the fraction of non-zero's in the two time series. Numerical experiments confirm the speed advantage of CSDTW relative to constrained DTW for sparse time series with sparsity ratio up to 0.2-0.3. This study provides a benchmark and also background to potentially understand how to exploit such sparsity when the underlying time series is approximated to reduce complexity.

Chronic diseases, such as heart disease, diabetes, and obesity, have been linked with diet. Nutrient intake is also associated with diet. However, much of the research completed to elucidate these associations has not incorporated the concept of time. This paper introduces the concept of temporal dietary patterns and demonstrates a novel construct of 24-hour temporal dietary patterns for energy intake, present in a sample of the adult U.S. population 20 years and older (NHANES 1999-2004 dataset). An appropriate distance metric is proposed for comparing 24-hour diet records and is used with kernel k-means clustering to identify the temporal dietary patterns.

The goal of this paper is to develop equalizers which can provide soft information to channel decoders for use in the single or the initial stage of iteration, of equalization and decoding architectures, especially for difficult channel to equalize. We propose an equalization structure by combining noncausality, bidirectionality and soft processing, and then we apply the soft noncausal and bidirectional DFE for North American HDTV terrestrial broadcast and EDGE cellular standard to examine its performance.

This paper is a study of high-performance soft-output demodulation for slow or moderate frequency-selective and flat Rayleigh fading using an autoregressive (AR) channel model. For channel taps modeled as AR processes, the discrete-time-equivalent channel model is derived for a matched filter (matched to the transmit pulse) and symbol rate-sampled receiver front end. The optimum symbol-by-symbol demodulator is then derived and shown to consist of a joint data and Kalman filter (KF) channel estimator. Additionally, a symbol-by-symbol demodulator with an extended KF is proposed that jointly identifies and tracks the channel and the unknown parameters in AR channel models. A simulation study shows that the proposed algorithms offer significant advantages in performance or complexity compared to several previously proposed algorithms. The algorithms do not exhibit a significant error floor, provide soft-output metrics needed for interleaved coded modulation, provide high performance with a blind initialization, are capable of blind operation with fast acquisition though compatible with pilot-symbol-assisted modulation, and are robust to parameter mismatch.

The allocation of available resources/subcarriers is an important design aspect for next generation wireless OFDM multiuser systems. The approaches considered usually assign a subset of subcarriers to each user and do not consider the loss of coding and diversity gains when a user is allotted very few subcarriers. We investigate an approach which exploits the multiplexing diversity available in the system in the absence of channel state information at the transmitter. This is achieved by spreading the data of all users over the complete set of subcarriers by using an appropriate combination of coding, multiplexing and interleaving. The performance of such a system is analyzed and the potential for substantial coding, interleaving and diversity gains is demonstrated. This paper also outlines a new approach to evaluate performance bounds for concatenated codes with higher order modulation on a fading multipath channel, by simplifying the description of pairwise error events using an ideal modulator assumption. Simulations are presented for a suboptimal decoding scheme, which does not rely on information from other users

Error propagation is a significant problem with the decision-feedback equalizer (DFE) at low-to-moderate signal-to-noise ratios. In particular, when a DFE is concatenated with a convolutional code, the burst errors associated with error propagation can severely degrade performance, since the convolutional code is optimized for the additive white Gaussian noise channel. In this paper, we explore the compensation of error propagation in the DFE so as to break up error bursts and improve performance with convolutional codes, without incurring larger overall decoding delay. We propose certain stationary error models and derive a modified DFE (MDFE) based on these models which can compensate for the error propagation. The MDFE differs from the conventional DFE only in its tap values. The incorporation of the bias into the model and the removal of the bias during the design process is discussed. Simulations explore the performance of the MDFE for both uncoded and convolutionally coded systems. With coding, the MDFE can significantly improve on the conventional DFE in terms of bit-error rate, and the MDFE without interleaving can improve on the conventional DFE with interleaving in terms of decision delay.

The paper outlines an efficient approach to evaluating the performance of bit interleaved coded modulation (BICM) systems. Most existing approaches evaluate the probability of individual pairwise error events and obtain a union bound to the bit error probability. This gives very tight bounds on performance for SNRs above the BPSK modulation cutoff rate. However, for higher order modulation systems, the number of bit errors in a symbol slot depends on the two modulated symbols involved in an error event and the linearity of the code cannot be extended to include the modulator. The performance is usually approximated by a few dominant error events which are applicable to AWGN channels. Some approaches consider infinite depth interleaving to obtain a simplified linear model. We study the evaluation and convergence of union bounds for fading channels with finite code block sizes. We develop a general approach which assumes an ideal model for the modulator and enables us to extend the linearity of the considered codes to simplify the computation. This enables us to analyze the performance of concatenated codes with an interleaver of finite length. The approach also gives greater insight into the influence of modulator parameters and the block length of the code on the diversity achieved in BICM systems. The application of our analytical model is demonstrated with examples and simulations.

Turbo equalization scheme provides nearly optimal performance but when it is employed in sparse multipath channel environments, the equalizer complexity can prohibit its use and develops a parallel trellis n-tap maximum a posteriori (MAP) equalizer, which can consider n dominant taps of sparse channels in the trellis with reasonable complexity. It is shown that turbo equalizations employing n-tap MAP equalizer can achieve nearly the same asymptotic performance of optimal maximum likelihood (ML) detector assuming perfect intersymbol interference (ISI) cancellation which is required for n-tap MAP. We also propose a tap allocation scheme for time-varying minimum mean squared error (MMSE) equalizer which can significantly reduce complexity and provide good tracking performance in time-varying channels.

This paper outlines an efficient approach to evaluate the performance of higher order coded modulated systems. Most of the approaches suggested so far have evaluated the probability of individual pairwise error events and obtained the union bound from the bit error probability. This gives a very tight bound on the performance of SNR's above cutoff rate for BPSK modulation. However, for higher order modulation systems, the number of bit errors in a symbol slot depends on the exact two modulated symbols involved in an error event. Due to computational complexity, the performance is usually approximated by a few dominant error events. The bounds thus obtained are only good for very high SNR's and AWGN channel. On the other hand, for a fading channel the correlation structure of the channel introduces another element of complexity. In this paper, we develop a general approach which assumes an ideal model for the modulator and enables us to extend the linearity of the considered codes to simplify the computation of the performance bounds for fading channels. This approach also gives a greater insight into the influence of modulator parameters on the performance of coded modulation systems. The application of our analytical model is demonstrated with examples and simulations.

When combining a multicode CDMA system with convolutional coding, two methods have been considered in the literature. In one method, coding is across time in each multicode channel while in the other the coding is across both multicodes and time. In this paper, a performance/complexity analysis of decoding metrics and trellis structures for the two schemes is carries out. It is shown that the latter scheme can exploit the multicode diversity inherent in convolutionally coded direct sequence code division multiple access (DS-CDMA) systems which employ minimum mean squared error (MMSE) error detectors. In particular, when the MMSE detector provides sufficiently different signal-to-interference ratios (SIR's) for the multicode channels, coding across multicodes and time can obtain significant performance gain over coding across time, with nearly the same decoding complexity.

The allocation of available resources in an OFDM multiaccess system is usually done by allotting a fixed set of subcarriers to each user. Adaptive allocation has been suggested to improve performance and provide increased granularity in terms of minimum number of subcarriers available to each user. But it has several drawbacks associated with the need for robust channel estimates and computational loading algorithms at the transmitter. In this paper, we investigate an approach which spreads the data of all the users over the complete set of subcarriers by appropriate combination of coding, multiplexing and interleaving. We analyze the performance of such a system and demonstrate the potential for substantial coding, interleaving and diversity gains relative to fixed subcarrier allocation, but with lower computational and signaling cost than adaptive schemes. We also present simulations for a suboptimal decoding scheme when the setup is applied to multiuser scenarios.

When combining a multicode CDMA system with convolutional coding, two methods have been considered in the literature. In one method, coding is across time in each multicode channel while in the other the coding is across both multicodes and time. In this paper, a performance/complexity analysis of decoding metrics and trellis structures for the two schemes is carried out. It is shown that the latter scheme can exploit the multicode diversity inherent in convolutionally coded direct sequence code division multiple access (DS-CDMA) systems which employ minimum squared error (MMSE) multiuser detectors. In particular, when the MMSE detector provides sufficiently different signal-to-reference ratios (SIRs) for the multicode channels, coding across multicodes and time can obtain significant performance gain over across time, with nearly the same decoding complexity.

Advanced receiver based techniques to alleviate the effects of nonlinear distortion in the bandlimited coded nonlinear satellite channel are considered. We propose a reduced complexity combined maximum likelihood equalization and decoding method using a nonlinear Volterra channel model in the trellis coded system. Our scheme includes conventional nonlinear compensation based on centroid estimation and decoding metric modification as a special case. Both analysis and simulation results show significant performance gain compared with separate Volterra equalization and decoding and also centroid estimation based decoding. Several methods of performance analysis in the nonlinear channel are discussed and compared.

A modified decision feedback equalizer (MDFE) which can compensate for error propagation was derived by Jung-Tao Lui and Gelfand (see Thirty-Six Annual Allerton Conference on Communication, Control, and Computing, 1998). The key property of the MDFE is its ability to shorten burst errors due to error propagation, and hence obtain an improved BER performance compared with the conventional DFE in a coded system. Here, we derive an LMS-type adaptive MDFE solution which incorporates the error propagation model into the training. The LMS MDFE is compared with the (offline) DFE and MDFE, and also two other adaptive DFE solutions found using an LMS algorithm with training data. Although slightly more complex than the other algorithms, the simulations suggest that the LMS MDFE has the best overall performance in a convolutionally coded system.

A recursive restoration algorithm based on a Markov random field model driven by Cauchy noise is described and demonstrated to provide better edge preservation than similar algorithms using Gaussian or Laplacian noises without increased computational cost.

In this paper, analytical performance bounds are presented for a hierarchical coded modulation system of the type which has been proposed for backward compatibility and/or variable error rate protection. This system uses two convolutional encoders (and two Viterbi (1989) decoders) with a hierarchical 16-QAM constellation, and is compatible with an existing QPSK based coded system. In the AWGN channel, we derive upper bounds for four different schemes (two decoding schemes, multi-stage decoding (MSD) and independent decoding(ID), and two labeling schemes, Gray labeling (GL) and non-Gray labeling (NGL)). We show that the performance of the simple GL with ID scheme is nearly optimum in the AWGN channel. Then we analyze the GL with ID scheme in the Rayleigh fading channel. Simulation results are given for comparison with the bounds.

Future CDMA systems may be required to operate with a low processing gain in order to accommodate high rate users. The resulting increase in channel dispersion will have a detrimental impact on code-timing acquisition. Two maximum-likelihood code-timing acquisition algorithms are proposed for multipath channels: a multiuser estimator and a single-user estimator. Multipath diversity is exploited in the estimators via maximum ratio combining to increase the signal-to-interference ratio. In addition, correlations between signals from different paths are explicitly incorporated in the test statistics of both estimators. Both help to improve the estimation accuracy and decrease mean acquisition time. Extensive simulations indicate that the estimators are robust to near-far power ratio and channel dispersion. Moreover, the gain achieved by incorporating channel dispersion in estimator design is significant.

Labeling and decoding schemes are compared for a backward-compatible hierarchical coded modulation system. This system, which is typical of recent proposals, uses two convolutional encoders (and two Viterbi decoders) with a hierarchical 16-QAM constellation, and is compatible with an existing QPSK based coded system. We derive upper bounds for four different schemes (two decoding schemes, multi-stage decoding and independent decoding, and two labeling schemes, Gray labeling and non-Gray labeling) in the AWGN channel. We show that the performance of the simple Gray labeling with independent decoding scheme is nearly optimum in the AWGN channel. Simulation results are given for comparison with the bounds.

Future CDMA systems will sometimes be required to operate with low processing gain in order to accommodate high rate users. The resulting increase in channel dispersion can have a detrimental impact on code-timing acquisition. Two maximum likelihood code-timing acquisition algorithms are proposed for multipath channels: a multiuser estimator and a single-user estimator. Multipath diversity is exploited in the estimators via maximum ratio combining to increase the signal-to-interference ratio. In addition, correlations between signals from different paths are explicitly incorporated in the test statistics of both estimators. The Cramer-Rao bounds are found and the performances of the estimators are examined via simulations. The results indicate that the estimators are robust to near-far power ratio and channel dispersion. Moreover, the gain achieved by incorporating channel dispersion in estimator design is significant.

We present an analytical method for computing the autocorrelation and conditional mean of the output of a bandlimited nonlinear amplifier. The method, which is applicable to modulations having /spl pi//2 symmetry, includes the effects of additive noise at the input to the nonlinear amplifier in addition to pulse shaping and the resulting intersymbol interference present in the nonlinear amplifier output. The autocorrelation and conditional mean calculations given in this paper form the basis of an analytical design method which may be used in several satellite communication problems including the design of amplifier output filtering, the joint optimization of pulse shaping and receiver filters, and the design of optimal data predistortion. The method of this paper provides an attractive alternative to Monte Carlo based designs in terms of both accuracy and computational complexity.

Two modified decision feedback equalization (DFE) structures are presented for the efficient equalization of long sparse channels with strong precursor, such as those encountered in high-speed communications over multipath channels with large delay spread. Unlike the conventional DFE, these structures allow the channel's sparseness to be exploited by simple tap allocation, before the sparseness is degraded by feedforward filtering. Both structures yield large reductions in complexity while maintaining performance comparable to the conventional DPE, hence overcoming a key computational bottleneck when equalizers are implemented in hardware for speed. Fast channel estimate-based algorithms for computing the modified DFE coefficients are derived. Simulation results are presented for data rates and channel profiles of the type considered for the proposed North American high definition television (HDTV) terrestrial broadcast mode.

We propose a novel approach to efficiently estimate multipath channel parameters, which is particularly useful in sparse multipath channels. Conventional methods do not fully exploit the inherent structure present in the combined channel response; the excess number of parameters to be estimated by conventional methods makes the identification difficult. By utilizing a priori knowledge of the transmission data pulse, the channel identification problem is transformed into the mode estimation problem. Then, the parameters directly related to the multipath propagation are extracted in the the modal analysis framework, and hence, the number of estimation parameters are significantly reduced. Finally, the multipath channel parameters are obtained by inverse-transforming the mode parameters. Simulation results show significant improvement in the normalized mean square error over existing approaches.

Decision feedback equalization (DFE) structures have been proposed for the efficient equalization of wireless channels with long postcursor response, which is a bottleneck problem for high speed communications over multipath channels with large delay spread. These structures are equivalent to the conventional DFE, but remove postcursor intersymbol interference (ISI) prior to feedforward filtering. We investigate the relationship between these structures and fast equalizer coefficient computation. Based on this relationship, we obtain a fast algorithm for computing optimal DFE settings which has significantly lower complexity than other known approaches for these high speed wireless channels. An example is given for data rates and channel profiles of the type considered for the proposed North American high definition television (HDTV) terrestrial broadcast mode.

We consider recursive estimation of images modeled by non-Gaussian autoregressive (AR) models and corrupted by spatially white Gaussian noise. The goal is to find a recursive algorithm to compute a near minimum mean square error (MMSE) estimate of each pixel of the scene using a fixed lookahead of D rows and D columns of the observations. Our method is based on a simple approximation that makes possible the development of a useful suboptimal nonlinear estimator. The algorithm is first developed for a non-Gaussian AR time-series and then generalized to two dimensions. In the process, we draw on the well-known reduced update Kalman filter (KF) technique of Woods and Radewan to circumvent computational load problems. Several examples demonstrate the non-Gaussian nature of residuals for AR image models and that our algorithm compares favorably with the Kalman filtering techniques in such cases.

The stability of variable stepsize LMS (VSLMS) algorithms with uncorrelated stationary Gaussian data is studied. It is found that when the stepsize is determined by the past data, the boundedness of the step size by the usual stability condition of fixed stepsize LMS is sufficient for the stability of VSLMS. When the stepsize is also related to the current data, the above constraint is no longer sufficient. Instead, both the upper bound and the lower bound of the stepsize must be within a smaller region. An exact expression of the stability region is developed for a single tap filter. The results are verified by computer simulations.

In many identification and tracking problems, an accurate estimate of the measurement noise variance is available. A partially adaptive LMS-type algorithm is developed which can exploit this information while maintaining the simplicity and robustness of LMS. This noise constrained LMS (NCLMS) algorithm is a type of variable step-size LMS algorithm, which is derived by adding constraints to the mean-square error optimization. The convergence and steady-state performance are analyzed. Both the theoretical results and simulations show that NCLMS can dramatically outperform LMS, RLS and other variable step-size LMS algorithms in a sufficiently noisy environment.

We consider recursive estimation of images modeled by non-Gaussian autoregressive (AR) models and corrupted by spatially white Gaussian noise. The goal is to find a recursive algorithm to compute a near minimum mean squared error (MMSE) estimate of each scene pixel using a fixed lookahead of D rows and D columns of the observations. Our method is based on a simple approximation which facilitates the development of a useful suboptimal nonlinear estimator. In the process, we draw on the well-known reduced update Kalman filter to circumvent computational load problems. A simulation example demonstrates the non-Gaussian nature of the residual for an AR image model and that our algorithm compares favourably with Kalman filtering techniques in such cases.

This paper introduces a new family of deconvolution filters for digital communications subject to severe intersymbol interference. These fixed lag smoothing filters for known channel demodulation are called Bayesian filters. Bayesian filters are derived using a new approach to suboptimal recursive minimum mean square error estimation for non-Gaussian processes. The family of Bayesian filters interpolates between the optimum fixed lag linear filter (i.e., the Kalman filter) and the optimum fixed lag symbol-by-symbol demodulator in both performance and complexity. The complexity of the Bayesian filter is exponential in a parameter, typically chosen smaller than the channel length and the filter lag. Hence, the Bayesian filter decouples the channel length and the filter lag from the exponential complexity in these parameters found in many other high performance demodulation algorithms. Simulations characterize the performance and compare the Bayesian filter to both optimal and reduced complexity demodulation algorithms.

This paper introduces extended Bayesian filters (EBFs), a new family of blind deconvolution filters for digital communications. The blind deconvolution problem is formulated as a nonlinear and non-Gaussian fixed-lag minimum mean square error filtering problem, and the EBF is derived as a suboptimal recursive estimator. The model-based setting makes extensive use of the transmitted symbol and noise distributions. A key feature of the EBF is that the filter lag can be chosen to be larger than the channel length, while the complexity is exponential in a parameter which is typically chosen to be smaller than both the channel length and the filter lag. Extensive simulations characterizing the performance of EBFs in severe intersymbol interference channels are presented. The fast convergence and robust equalization of the EBFs are demonstrated for uncoded linearly modulated signals [e.g., differentially encoded quaternary phase shift keying (QPSK)] transmitted over unknown channels. Comparisons are made to other blind symbol-by-symbol demodulation algorithms. The results show that the EBF provides much better performance (at increased complexity) compared to the constant modulus algorithm and the extended Kalman filter, and achieves a better performance-complexity trade-off than other Bayesian demodulation algorithms. The simulations also show that the EBF is applicable with large constellations and shaped modulations.

We present real-time algorithms for the segmentation of binary images modeled by Markov mesh random fields (MMRFs) and corrupted by independent noise. The goal is to find a recursive algorithm to compute the maximum a posteriori (MAP) estimate of each pixel of the scene using a fixed lookahead of D rows and D columns of the observations. First, this MAP fixed-lag estimation problem is set up and the corresponding optimal recursive (but computationally complex) estimator is derived. Then, both hard and soft (conditional) decision feedbacks are introduced at appropriate stages of the optimal estimator to reduce the complexity. The algorithm is applied to several synthetic and real images. The results demonstrate the viability of the algorithm both complexity-wise and performance-wise, and show its subjective relevance to the image segmentation problem.

We present real-time algorithms for the segmentation of binary images modeled by Markov mesh random fields (MMRFs) and corrupted by independent noise. The goal is to find a recursive algorithm to compute the MAP estimate of each pixel of the scene using a fixed lookahead of D rows and D columns of the observations. The optimal algorithm for this is computationally expensive. Using both hard and soft (conditional) decision feedback, the complexity is reduced in a principled manner to allow a performance/complexity tradeoff. Simulation results demonstrate the viability of the algorithm and it's subjective relevance to the image segmentation problem.

There has been great interest in reduced complexity suboptimal MAP symbol-by-symbol estimation for digital communications. We propose a new suboptimal estimator suitable for both known and unknown channels. In the known channel case, the MAP estimator is simplified using a form of conditional decision feedback, resulting in a family of Bayesian conditional decision feedback estimators (BCDFEs); in the unknown channel case, recursive channel estimation is combined with the BCDFE. The BCDFEs are indexed by two parameters: a "chip" length and an estimation lag. These algorithms can be used with estimation lags greater than the equivalent channel length and have a complexity exponential in the chip length but only linear in the estimation lags. The BCDFEs are derived from simple assumptions in a model-based setting that takes into account discrete signalling and channel noise. Extensive simulations characterize the performance of the BCDFE and BCDPE for uncoded linear modulations over both known and unknown (nonminimum phase) channels with severe ISI. The results clearly demonstrate the significant advantages of the proposed BCDFE over the BCDFE in achieving a desirable performance/complexity tradeoff. Also, a simple adaptive complexity reduction scheme can be combined with the BCDFE resulting in further substantial reductions in complexity, especially for large constellations. Using this scheme, we demonstrate the feasibility of blind 16QAM demodulation with 10/sup -4/ bit error probability at E/sub b//N/sub 0//spl ap/ 18.5 dB on a channel with a deep spectral null.>

This paper applies the Bayesian conditional decision feedback estimator (BCDFE) to rapidly fading frequency selective channels. The BCDFE is a model-based deconvolution algorithm which jointly estimates the transmitted data and channel parameters. The BCDFE applies joint symbol-by-symbol MAP demodulation and channel estimation to equalize channels, and consequently provides robust performance in rapidly fading channels. We provide a brief derivation of the BCDFE and characterize the performance on the land mobile radio channel. We assess the BCDFE's principle design characteristics and the resulting performance in both transient and steady-state operation. The effects of delay spread, Doppler spread, and co-channel interference on the BEP performance are also presented. The BCDFE demonstrates many of the desirable characteristics of an equalizer for mobile radio.>

The use of a tree-structured piecewise linear filter as an adaptive equalizer is proposed. In the tree equalizer, each node in a tree is associated with a linear filter restricted to a polygonal domain, and each subtree is associated with a piecewise linear filter. A training sequence is used to adaptively update the filter coefficients and domains at each node, and to select the best subtree and corresponding piecewise linear filter. The tree-structured approach offers several advantages. First, it makes use of standard linear adaptive filtering techniques at each node to find the corresponding conditional linear filter. Second, it allows for efficient selection of the subtree and corresponding piecewise linear filter of appropriate complexity. Overall, the approach is computationally efficient and conceptually simple. Numerical experiments are performed to show the advantages of tree-structured piecewise linear and piecewise decision feedback equalizers over linear, polynomial, and decision feedback equalizers for the equalization of channels with severe intersymbol interference.>

The authors propose and analyze a novel architecture for nonlinear adaptive filters. These nonlinear filters are piecewise linear filters obtained by arranging linear filters and thresholds in a tree structure. A training algorithm is used to adaptively update the filter coefficients and thresholds at the nodes of the tree, and to prune the tree. The resulting tree-structured piecewise linear adaptive filter inherits the robust estimation and fast adaptation of linear adaptive filters, along with the approximation and model-fitting properties of tree-structured regression models. A rigorous analysis of the training algorithm for the tree-structured filter is performed. Some techniques are developed for analyzing hierarchically organized stochastic gradient algorithms with fixed gains and nonstationary dependent data. Simulation results show the significant advantages of the tree-structured piecewise linear filter over linear and polynomial filters for adaptive echo cancellation.>

The use of small multilayer nets at the decision nodes of a binary classification tree to extract nonlinear features is proposed. This approach exploits the power of tree classifiers to use appropriate local features at the different levels and nodes of the tree. The nets are trained and the tree is grown using a gradient-type learning algorithm in conjunction with a heuristic class aggregation algorithm. The method improves on standard classification tree design methods in that it generally produces trees with lower error rates and fewer nodes. It also provides a structured approach to neural network classifier design which reduces the problem associated with training large unstructured nets, and transfers the problem of selecting the size of the net to the simpler problem of finding the right size tree. Example concern waveform and handwritten character recognition.>

The authors cast edge detection as a problem in cost minimization. This is achieved by the formulation of a cost function that evaluates the quality of edge configurations. The function is a linear sum of weighted cost factors. The cost factors capture desirable characteristics of edges such as accuracy in localization, thinness, and continuity. Edges are detected by finding the edge configurations that minimize the cost function. The authors give a mathematical description of edges and analyze the cost function in terms of the characteristics of the edges in minimum cost configurations. Through the analysis, guidelines are provided on the choice of weights to achieve certain characteristics of the detected edges. The cost function is minimized by the simulated annealing method. A set of strategies is presented for generating candidate states and to devise a suitable temperature schedule.>

The ideal use of small multilayer nets at the decision nodes of a binary classification tree to extract nonlinear features is proposed. The nets are trained and the tree is grown using a gradient-type learning algorithm in the multiclass case. The method improves on standard classification tree design methods in that it generally produces trees with lower error rates and fewer nodes. It also reduces the problems associated with training large unstructured nets and transfers the problem of selecting the size of the net to the simpler problem of finding a tree of the right size. An efficient tree pruning algorithm is proposed for this purpose. Trees constructed with the method and the CART method are compared on a waveform recognition problem and a handwritten character recognition problem. The approach demonstrates significant decrease in error rate and tree size. It also yields comparable error rates and shorter training times than a large multilayer net trained with backpropagation on the same problems.

The idea of a tree-structured piecewise linear adaptive filter is proposed. The tree-structured filter is constructed as follows. Each node in a binary tree is associated with a linear filter restricted to a polygonal domain, and this is done in such a way that each subtree is associated with a piecewise linear filter. A training sequence is used to adaptively update the filter coefficients and domains at each node, and to select the best subtree and the corresponding piecewise linear filter. The authors summarize the derivation and analysis of the tree-structured piecewise linear adaptive filter. They then investigate the performance of the tree-structured filter as an adaptive echo canceler and compare it with that of linear and truncated Volterra series adaptive echo cancelers through computer simulations.>

A critical issue in classification tree design-obtaining right-sized trees, i.e. trees which neither underfit nor overfit the data-is addressed. Instead of stopping rules to halt partitioning, the approach of growing a large tree with pure terminal nodes and selectively pruning it back is used. A new efficient iterative method is proposed to grow and prune classification trees. This method divides the data sample into two subsets and iteratively grows a tree with one subset and prunes it with the other subset, successively interchanging the roles of the two subsets. The convergence and other properties of the algorithm are established. Theoretical and practical considerations suggest that the iterative free growing and pruning algorithm should perform better and require less computation than other widely used tree growing and pruning algorithms. Numerical results on a waveform recognition problem are presented to support this view.>

Edge detection is analyzed as a problem in cost minimization. A cost function is formulated that evaluates the quality of edge configurations. A mathematical description of edges is given, and the cost function is analyzed in terms of the characteristics of the edges in minimum-cost configurations. The cost function is minimized by the simulated annealing method. A novel set of strategies for generating candidate states and a suitable temperature schedule are presented. Sequential and parallel versions of the annealing algorithm are implemented and compared. Experimental results are presented.>

An efficient iterative method is proposed to grow and prune classification trees. This method divides the data sample into two subsets and iteratively grows a tree with one subset and prunes it with the other subset, successively interchanging the roles of the two subsets. The convergence and other properties of the algorithm are established. Theoretical and practical considerations suggest that the iterative tree growing and pruning algorithm should perform better and require less computation than other widely used tree growing and pruning algorithms. Numerical results on a waveform recognition problem are presented to support this view.>

Edge detection is cast as a problem in cost minimization. The concept of an edge that is based on criteria such as accurate localization, thinness, continuity, and length is described. On the basis of this description, a comparative cost function that mathematically captures the intuitive idea of an edge is formulated. The function uses information from both image data and local edge structure in evaluating the relative quality of pairs of edge configurations. The function is a linear combination of weighted cost factors. Computation of the function is performed efficiently by organizing information in the form of a decision tree. Edges are detected using a heuristic iterative search algorithm based on the comparative cost function. The detection process can be implemented largely in parallel. The usefulness of this approach to edge detection is demonstrated by showing experimental results of detected edges for both real and synthetic images.>