ABSTRACT We revisit the problem of finding the shortest path between two selected vertices of a graph and formulate this as an ‐regularized regression—Least Absolute Shrinkage and Selection Operator (lasso). We draw connections between a numerical implementation of this lasso formulation, using the so‐called LARS algorithm, and a more established algorithm known as the bi‐directional Dijkstra. Appealing features of our formulation include the applicability of the Alternating Direction of Multiplier Method (ADMM) to the problem to identify short paths, and a relatively efficient update to topological changes.

We introduce and compare certain distance measures between covariance matrices. These originate in information theory, quantum mechanics and optimal transport. More specifically, we show that the Bures/Hellinger distance between covariance matrices coincides with the Wasserstein-2 distance between the corresponding Gaussian distributions. We also note that this Bures/Hellinger/Wasserstein distance can be expressed as the solution to a linear matrix inequality (LMI). A consequence of this fact is that the computational cost in covariance approximation problems scales nicely with the size of the matrices involved. We discuss the relevance of this metric in spectral-line detection and spectral morphing.

We present an intrinsic metric that quantifies distances between power spectral density functions. The metric was derived by Georgiou as the geodesic distance between spectral density functions with respect to a particular pseudo-Riemannian metric motivated by a quadratic prediction problem. We provide an independent verification of the metric inequality and discuss certain key properties of the induced topology.

The maximum entropy (ME) principle, as it is often invoked in the context of time-series analysis, suggests the selection of a power spectrum which is consistent with autocorrelation data and corresponds to a random process least predictable from past observations. We introduce and compare a class of spectra with the property that the underlying random process is least predictable at any given point from the complete set of past and future observations. In this context, randomness is quantified by the size of the corresponding smoothing error and deterministic processes are characterized by integrability of the inverse of their power spectral densities - as opposed to the log-integrability in the classical setting. The power spectrum which is consistent with a partial autocorrelation sequence and corresponds to the most random (MR) process in this new sense, is no longer rational but generated by finitely many fractional-poles.

We present a technique for spectral analysis in the context of multi-rate sampling by a collection of sensors. Correlation of the time-domain samples gives rise to moment constraints for the power spectrum. A homotopy-based technique is then used to identify consistent power spectra. The spectra we obtain are at a minimum distance in the Kullback-Leibler sense to a given "prior" and the "maximum entropy" power spectrum corresponds to the special case where the prior is white

We point out that autocovariance functions of moving average processes of any given order m can be characterized via a linear matrix inequality (LMI). This LMI-condition can be used to decompose any Toeplitz autococovariance matrix into a sum of a singular Toeplitz covariance plus the autocovariance matrix of a moving average process of order m and of maximal variance. The decomposition is unique and subsumes the Pisarenko harmonic decomposition that corresponds to m=0. It can be used to account for mutual couplings between elements in linear antenna arrays or identify colored noise consistent with the covariance data. The same LMI-condition leads to an efficient computation of the least order of a MA-spectrum that agrees with covariance moments

Entropy-like functionals on operator algebras have been studied since the pioneering work of von Neumann, Umegaki, Lindblad, and Lieb. The best known are the von Neumann entropy |(rho):=-trace(rhologrho) and a generalization of the Kullback- Leibler distance S(rhoparsigma):=trace(rhologrho-rhologsigma), referred to as quantum relative entropy and used to quantify distance between states of a quantum system. The purpose of this paper is to explore | and S as regularizing functionals in seeking solutions to multivariable and multidimensional moment problems. It will be shown that extrema can be effectively constructed via a suitable homotopy. The homotopy approach leads naturally to a further generalization and a description of all the solutions to such moment problems. This is accomplished by a renormalization of a Riemannian metric induced by entropy functionals. As an application, we discuss the inverse problem of describing power spectra which are consistent with second-order statistics, which has been the main motivation behind the present work

In direction finding of narrow-band signals using antenna arrays with a large number of elements, the so-called beamspace matrix is often used to project the measurements into a lower dimension subspace. This reduces computation time and allows for parallel processing. On the other hand, beamspace preprocessing may introduce ambiguity, i.e., spurious estimated directions. We show that when the null space of the beamspace matrix is suitably designed, ambiguity within any sector of interest can be avoided.

We introduce a Kullback-Leibler (1968) -type distance between spectral density functions of stationary stochastic processes and solve the problem of optimal approximation of a given spectral density /spl Psi/ by one that is consistent with prescribed second-order statistics. In general, such statistics are expressed as the state covariance of a linear filter driven by a stochastic process whose spectral density is sought. In this context, we show (i) that there is a unique spectral density /spl Phi/ which minimizes this Kullback-Leibler distance, (ii) that this optimal approximate is of the form /spl Psi//Q where the "correction term" Q is a rational spectral density function, and (iii) that the coefficients of Q can be obtained numerically by solving a suitable convex optimization problem. In the special case where /spl Psi/ = 1, the convex functional becomes quadratic and the solution is then specified by linear equations.

The state-covariance of a linear filter imposes a generalized interpolation constraint on the power spectrum of the input. We explore this observation by first characterizing minimal line-spectra which are consistent with given state-covariance data. In particular, we present a canonical decomposition for state-covariances which is analogous to the well-known decomposition of Toeplitz matrices due to Caratheodory-Fejer and Pisarenko. Accordingly we develop subspace-based signal estimation techniques which apply to state covariances of linear filters and are analogous to MUSIC and ESPRIT. A method analogous to one due to Capon, but based on state-covariance data instead, is also presented. Finally, through a certain duality, subspace methods are shown to be useful in identifying absorption instead of emission lines in the power spectrum of the filter-input.

It is well known that the maximum likelihood (ML) spectral estimate represents an envelope on spectral power which is consistent with estimated covariance lags. However, in computing the envelope, the ML method allows for spectra corresponding to complex-valued stochastic processes. We study the respective envelope for processes constrained to be real-valued at the outset. The resulting envelope is less conservative than the one provided by the ML method. A closed form expression exists for the new envelope.>

This paper presents new results on the problem of realization of a power spectrum of a stochastic process from a given set of error-free covariance samples (spectral estimation). This problem is known in the mathematical literature as the Caratheodory problem and has been studied extensively. We present a novel topological approach (as opposed to algebraic and function-theoretic ones that have been developed classically) which enables us to address certain questions about the degree of the interpolating functions, or, equivalently, the dimension of associated stochastic realizations. A new class of recursive spectral estimators is also introduced. These are tailored to make use of the nonuniqueness that is inherent when obtaining realizations of a certain dimension.