Adaptation using contravariant, sometimes called the natural gradient, provides true steepest descent learning on a manifold such as the manifold of invertible matrices or the manifold of invertible matrix transfer functions. In this letter, the contravariant gradient on the manifold of invertible matrix transfer functions is presented using the language of differential geometry. The covariant gradient (the usual gradient) is converted to the contravariant or natural gradient using the inverse of a Riemannian metric tensor, which is derived for the manifold of invertible matrix transfer functions. This has not been previously done using the language of differential geometry.

This letter extends previous work on contravariant adaptation by providing a formula for the contravariant (natural) gradient on the manifold of multivariable, causal, invertible, finite impulse response (FIR) systems. The right action on the manifold of multivariable causal Toeplitz systems is defined. Using this right action, a bilinear form defined on the tangent space at the identity is extended throughout the entire manifold by invariance. This results in a formula analogous to the natural gradient for matrices, but which preserves the causal, FIR nature of the system. The contravariant conversion factor is block Toeplitz structured, so that implementations may employ fast Fourier transform based convolutions to produce lower complexity than would a comparably-sized generic matrix natural gradient.

This paper addresses the video processing problem of passively estimating the heart rate of a human subject that is being video recorded in ambient light in natural conditions in which some motion is allowable. This extends previous work in which control over lighting and motion are required. A mathematical model is developed for the measured pixels on the subject's forehead. This model includes (1) a Markov process that accounts for the large scale but slowly fluctuating variations in reflected light, and (2) a quasi-periodic process to model the relatively small heart beat component. A framework for estimating these components is proposed and results of applying this method to real data recordings is presented. Results are compared to heart rate obtained from a pulse oximeter attached to the subject's finger.

Simultaneously estimating position and velocity of moving targets using only phase information from single-channel SAR data is impossible. This paper defines classes of equivalent target motion and solves the GMTI problem up to membership in an equivalence class using single-channel SAR phase data. We present a definitions for endo- and exo-clutter that is consistent with the equivalence classes, and show that most target motion can be detected, i.e. the set of endo-clutter targets is very small. We exploit the sparsity of moving targets in the scene to develop an algorithm to resolve target motion up to membership in an equivalence class, and demonstrate the effectiveness of the proposed technique using simulated data.

Digital down-conversion in software defined radios in space-to-Earth and Earth-to-space communications is challenging due to potentially large Doppler frequency offsets. The predictability of satellite orbits suggests that a computed Doppler offset could be used to perform an orbit-informed down-conversion. However, publicly available orbital parameters and orbit propagator codes lack the accuracy required for fine Doppler removal. This paper proposes a technique to adjust the orbital parameters until the computed Doppler profile matches the Doppler profile in the received signal. This technique is applied to a real signal recorded from a satellite overpass and is shown to be able to very accurately estimate frequency offsets.

Speech recognition is a classic example of a human/machine interface, typifying many of the difficulties and opportunities of human/machine interaction. In this paper, speech recognition is used as an example of applying turbo processing principles to the general problem of human/machine interface. Speech recognizers frequently involve a model representing phonemic information at a local level, followed by a language model representing information at a nonlocal level. This structure is analogous to the local (e.g., equalizer) and nonlocal (e.g., error correction decoding) elements common in digital communications. Drawing from the analogy of turbo processing for digital communications, turbo speech processing iteratively feeds back the output of the language model to be used as prior probabilities for the phonemic model. This analogy is developed here, and the performance of this turbo model is characterized by using an artificial language model. Using turbo processing, the relative error rate improves significantly, especially in high-noise settings.

In some modeling scenarios, particularly those representing data from natural sources, the discrete states conventionally used in hidden Markov models (HMMs) are at best an approximation, since the discrete states are a modeling artifact. In this paper we present an HMM in which the states take any value in a simplex. The Dirichlet distribution is used to provide a parsimonious representation of the distribution of the states. Conditional state estimates using an extension of the conventional forward/backward method, using Dirichlet distributions to provide a nearly closed-form, but approximate, representation.

This paper develops a receiver for a multiple access scenario obtained by simply overlaying transmitted signals from different users, with (essentially) the same carrier, same modulation format, etc., without the benefit of conventional multiple access signaling. A joint a posteriori probability detector is derived for co-received signals. The receiver structure follows the familiar general model for turbo processing, employing a soft-in-soft-out joint detector followed by error correction decoding, which feeds back soft information in the form of extrinsic probabilities. Since the receiver is intended to function with an existing transmission system with no modifications to the transmitter, channelization methods and/or interleavers which would normally be designed into a multi-access system are absent. The general structure is demonstrated using a system employing LDPC decoding and simulated performance results are presented.

Several authors have developed a Hadamard (variously called FFT) transform technique for fast belief propagation over$GF(q)$, where in all prior work$q=2^{m}$for some$m$. The belief propagation step which employs the transform generalizes Gallager's lemma for computing the distribution of a sum of variables over a finite field. In this paper, the limitation to fields of characteristic 2 is eliminated, so that computations can take place over finite fields of arbitrary prime characteristic. This opens the door, for example, for BP decoding algorithms over the same fields that are used for algebraic geometry codes.

A unique Research Experience for Undergraduates (REU) was offered at Utah State University in the summer of 2009, with research topics drawn from signal processing, digital communications, and error correction coding. Thirteen students participated in this ten-week program, working on nine separate projects. The program began with two weeks of intense instruction with five accompanying programming and writing assignments. Students were presented with a number of projects to choose from according to their preparation and preference, developing in them the independence and “buy in” necessary for effective original research. Regular social activities were also planned to develop the research team and keep energy up. Results include several conference and journal papers and contributions to other ongoing research projects.

An iterative least square method is presented for estimating the solution to the lidar equation. The method requires knowledge of the backscatter values at a boundary point for all channels and a priori defined relationships between backscatter, extinction, and mass-fraction concentration for all scattering components. The lidar equation is formulated in vector form, and a solution is computed using an iterative least square technique. The solution is stable for signals with extremely low signal-to-noise ratios and for signals at ranges far beyond the boundary point. The solution can be applied to lidar signals with an arbitrary number of wavelengths and scattering components.

This paper explores the use of kurtosis in synchronizing with a QPSK burst transmission. The start and end of the burst are a priori unknown and are detected without the use of pilot signals. After frame level synchronization, signal level synchronization is performed. The symbol timing, carrier frequency and carrier phase are recovered without the assistance of known symbols or synchronization words in the data stream, i.e. totally blind synchronization. The performance of frame, symbol and carrier synchronization algorithms is evaluated through computer simulations.

The eigenmessage approach to iterative decoding introduces a degree of nonlocality into a belief propagation decoder by representing an entire set of messages around a cycle of the Tanner graph as a linear operator. The eigenvector for the operator represents a fixed point of the belief propagation algorithm around a cycle, with incident messages fixed. A multiple eigenmessage approach is also presented, in which messages around several cycles are simultaneously expressed. The eigenmessage approach may be applied to any graph with cycles, but we demonstrate its use on LDPC decoding. In this setting, computational results compare eigenmessage methods with conventional belief propagation decoding showing, using simulation and EXIT charts, that the eigenmessage approaches slightly reduce the number of decoder iterations compared to belief propagation decoding while preserving the probability of error of conventional decoding.

The Sudoku puzzle is a discrete constraint satisfaction problem, as is the error correction decoding problem. We propose here an algorithm for solution to the Sinkhorn puzzle based on Sinkhorn balancing. Sinkhorn balancing is an algorithm for projecting a matrix onto the space of doubly stochastic matrices. The Sinkhorn balancing solver is capable of solving all but the most difficult puzzles. A proof of convergence is presented, with some information theoretic connections. A random generalization of the Sudoku puzzle is presented, for which the Sinkhorn-based solver is also very effective.

By using a formulation similar to a Sobolev gradient for the natural gradient a new algorithm has been developed that converges faster, uses fewer additional parameters and has smaller storage requirements all while not overtraining to a training set. Simulation results show the improvements for an applicable problem.

Frequency-domain least-squares filter design is extended to the case that magnitude and phase are not specified for all test frequencies. Unspecified quantities are obtained by an iterative, alternating projection algorithm. Examples of gain-only and phase-only identification are provided, as well as filter design.

The well-known Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm was generalized to compute joint posterior probabilities of arbitrary sets of symbols given noisy observations of those symbols at the output of an intersymbol interference (ISI) channel. This letter explores using pair-wise joint posterior probabilities produced by generalized BCJR together with expectation maximization for blind identification of the ISI channel impulse response and noise variance. Simulations indicate that the blind algorithm accurately estimates the channel response and noise variance and yields bit error rates comparable to a channel-informed BCJR equalizer.

Natural gradient learning has been shown to avoid singularities in the parameter space of multilayer perceptrons. However, it requires a large number of additional parameters beyond ordinary backpropagation. The article describes a new approach to natural gradient learning in which the number of parameters necessary is much smaller than in the natural gradient algorithm. This new method exploits the algebraic structure of the parameter space to reduce the space and time complexity of the algorithm and improve its performance.

A generalization of the BCJR algorithm is derived to compute joint posterior probabilities of arbitrary sets of symbols given received data. A special case of the new algorithm that computes pairwise joint probabilities is used to evaluate the second order statistics needed for EM estimation of carrier phase and symbol timing offsets in a digitally modulated waveform. This EM estimator is integrated into a turbo synchronization loop in which soft information is exchanged between the generalized BCJR algorithm (the synchronizer) and an LDPC decoder.

We present two lemmas relating polynomials occurring in the derivations of the Welch-Berlekamp (WB) key equation for Reed-Solomon codes. The lemma provides the connection between the conventional Welch-Berlekamp form of the key equation and the nullspace-based derivation of Dabiri and Blake. The second lemma allows the error values for the Dabiri Blake formulation to be computed based on the error values for the Welch-Berlekamp form.

We consider the problem of estimating the feedback coefficients of a linear feedback shift register based on noisy observations. The problem of determining feedback coefficients in the absence of noise is now classical (Massey's (1969) algorithm). In the current approach to the problem of estimation with noisy observations, the coefficients are endowed with a probabilistic model. Gradient ascent updates to coefficient probabilities are computed using recursions developed by means of the expectation-maximization (EM) algorithm. Reduced-complexity approximations are also developed by reducing the number forward probability terms propagated at each stage. While suffering from a local-maximum problem typical of many maximum-likelihood (ML) procedures, the method does exhibit convergence.

In this paper, we characterize optimal detection and signaling (in terms of signal-to-noise ratio) for a fast fading channel when the autocorrelation function of the channel variation is known. We find that the well known matched filter and RAKE receiver are limiting cases of our result. Also, we provide a procedure that finds a pair of signals for digital communication. With land mobile fading channels, the signals obtained with our procedure have a performance significantly better than traditional flat-top pulse in terms of probability of error rate.

We consider the problem of estimating the feedback coefficients of a linear feedback shift register (LFSR) based on noisy observations. In the current approach, the coefficients are endowed with a probabilistic model. Gradient ascent updates to coefficient probabilities are computable using recursions developed by means of the EM algorithm. Reduced-complexity approximations are also developed by reducing the number of coefficients propagated at each stage. Applications of this method may include soft decision decoding and blind spread spectrum interception.

Reversible T-codes are codes which are self-synchronizing and are prefix codes when read in both the forward and backward direction. The reverse decoding provides for recovery of bits used in synchronization, and further means that bit strings can be tied, meaning both ends are known to be at codeword boundaries. Having tied bit strings leads do an algorithm which can provide partial bit recovery in erasure channels, such as packetized Internet UDP channels. Comparisons of reversible T-codes with non-reversible T-codes and Huffman codes are provided.

This paper points out two potential problems with residual vector quantization (RVQ): tree entanglement and non-projectiveness of the quantizer. The use of a boundary normalization mapping is proposed to pool all quantization residuals at a stage into identically-shaped regions, reducing or eliminating entanglement. Also, a reconstruction codebook is proposed to eliminate the non-projectiveness is proposed. Results are presented on both random and image data.

Many of the previously-developed multiple-access detection algorithms have assumed knowledge of the time delay, the amplitude, and the phase of each user. This paper presents methods of estimating the amplitudes and phases, both when the time delays are known and when the delays are unknown. In neither case are the transmitted bits assumed to be known. The estimators are unbiased and consistent, and each has a computational complexity linear in the number of users. Simulations are provided to demonstrate performance.>

We consider the problem of using Levi's expected epistemic decision theory for classification when the hypotheses are of different informational values, conditioned on convex sets obtained from a set-valued Kalman filter. The background of epistemic utility decision theory with convex probabilities is outlined and a brief introduction to set-valued estimation is given. The decision theory is applied to a classifier in a multiple-target tracking scenario. A new probability density, appropriate for classification using the ratio of intensities, is introduced.>

A decision philosophy that seeks the avoidance of error by trading off belief of truth and value of information is applied to the problem of recognizing tracks from multiple targets (MTT). A successful MTT methodology should be robust in that its performance degrades gracefully as the conditions of the collection become less favorable to optimal operation. By stressing the avoidance, rather than the explicit minimization, of error, the authors obtain a decision rule for trajectory-data association that does not require the resolution of all conflicting hypotheses when the database does not contain sufficient information to do so reliably. This rule, coupled with a set-valued Kalman filter for trajectory estimation, results in a methodology that does not attempt to extract more information from the database than it contains.>

We present a new algorithm for coefficient selection during image compression using the wavelet transform for decomposition and reconstruction. This new algorithm assigns a weight to each scale so that coefficients from a high resolution scale are more likely to be discarded before coefficients from a low resolution scale. Results show our algorithm introduces less error into the reconstructed image than the sort method developed by DeVore/em et al.

The problem of simultaneously detecting the information bits and estimating signal amplitudes and phases in a K-user asynchronous direct-sequence spread-spectrum multiple-access communication system is addressed. The joint maximum-likelihood (ML) estimator has a computational complexity that is exponential in the total number of bits transmitted and thus does not represent a practical solution to the problem. An estimator that combines a suboptimum tree-search algorithm with a recursive least-squares estimator of complex signal amplitude is considered. The complexity of this estimator is O(K/sup 2/) computations per decoded bit, and its performance is very close to that of the joint ML receiver. This receiver has the advantage that the transmitted signal powers and phases are extracted from the received signal in an adaptive fashion without using a test sequence.>

A direct approach to the estimation of the parameters associated with a bilinear time series model is presented. The approach depends critically on the expressions for certain higher-order statistics of the signals that satisfy the bilinear model. These expressions are linear in most of the parameters of the model. The parameters are then estimated from an overdetermined set of equations. Results of an experiment that employs this technique and demonstrates its good properties are included.>