MSI Weekly Bulletin - Week starting Monday 15 May, 2006

Inverse eigenvalue problems for matrices come in many forms but they all require one to construct a matrix from prescribed spectral data subject to additional structural constraints on the matrix. In the case of the inverse eigenvalue problem for nonnegative matrices, the additional structural constraints are that the matrix entries be nonnegative, and the matrix many also be required to be stochastic or symmetric. Finding necessary and sufficient conditions for a list of numbers to be realizable as the eigenvalues of a nonnegative matrix has been a challenging area of research for over fifty years and this problem is still unsolved. While various necessary or sufficient conditions exist, the necessary conditions are usually too general while the sufficient conditions are too specific. Under a few special sufficient conditions, a nonnegative matrix with the desired spectrum can be constructed, however, in general, proofs of sufficient conditions are non-constructive. This talk will present numerical methods for solving the nonnegative inverse eigenvalue problems mentioned above. These methods are iterative in nature and utilize 'alternating projection' ideas. In the case that one would like to find a symmetric matrix, the algorithm is particularly simple with the main computational component of each iteration being an eigenvalue-eigenvector decomposition. The talk will include an overview of algorithm convergence properties, as well as some numerical results. The ideas presented in the talk should also be applicable to many other inverse eigenvalue problems.

Classical linear and quadratic discriminant functions are two very well-known tools that provide good lower dimensional views of class separability. Fisher\'s (Fisher, 1936) original approach in linear and quadratic discriminant analysis assumes normality of the underlying distributions and uses the sample moments to estimate the population parameters and the separating surfaces. These estimates, however, are highly sensitive to outliers and they are not reliable for heavy tailed distributions. In this talk we will discuss about two robust and distribution free alternatives for classification based on linear or nonlinear separating surfaces. One of these classifiers is motivated by Tukey\'s half-space depth (Tukey, 1975) while the other one uses the notion of regression depth due to Rousseeuw and Hubert (1999). These depth-based methods assume some specific finite dimensional parametric form of the discriminating surface and uses distribution geometry of the training data cloud to build the classifier.