Inverse problems of matrix data reconstruction

The purpose of this investigation is to develop theoretic understanding and numerical algorithms for model reconstruction so that the inexactness and uncertainty are reduced while certain specific conditions are satisfied. This research revolves around two specific topics---quadratic inverse eigenvalue problems and low rank approximations---and some other related problems, both in theory and in computation.;An immediate and the most straightforward application of the quadratic inverse eigenvalue problem would be the construction of a vibration system from its observed or desirable dynamical behavior. Its mathematical model is associated to the quadratic matrix polynomial Q (lambda) = Mlambda2 + Clambda + K whose eigenvalues and eigenvectors govern the vibrational behavior. Tremendous complexities and difficulties in recovering coefficient matrices M, C, K arise when the predetermined inner-connectivity among its elements and the mandatory nonnegativity of its parameters must be taken into account. Considerable efforts have been taken to derive theory and numerical methods for solving inverse eigenvalue problems, but techniques developed thus far can handle the inverse problems only on a case by case basis. The first contribution in this investigation is an efficient, reliable semi-definite programming technique for inverse eigenvalues problems subject to specified spectral and structural constraints. Of particular concern is the issue of inexactness of the prescribed or measured eigeninformation, which is almost inevitable in practice, since inaccurate data will affect the solvability of this inverse eigenvalue problem. To address this issue, a second contribution in this investigation is a methodical approach by using the notion of truncated QR decomposition to first determine whether a nearby inverse problem is solvable and, if it is so, the method computes the approximate coefficient matrices while providing an estimate of the residual error. Both methods enjoy the advantages of preserving inter-connectivity structures and other important properties embedded in the original problems. More importantly, both approaches allow more flexibilities and robustness in handling highly structured problems than other special-purpose algorithms.;Low rank approximations have become increasingly important and ubiquitous in this era of information. Generally, there is no unified approach because the technique often is data type dependent. This research studies and proposes new factorization techniques for three different type of data. The first algorithm aims to perform a nonnegative matrix factorization of a nonnegative data matrix by recasting the problem geometrically as the approximation of a given polytope on the probability simplex by a simpler polytope with fewer facets. This view leads to a convenient way of decomposing the data by computing the proximity map which, in contrast to most existing algorithm where only an approximate map is used, finds the unique and global minimum per iteration. The second algorithm investigates the factorization of integer matrices which is more realistic and important in informatics. Searching through the literature, it appears that there does not exist a suitable algorithm which can handle this type of problem well owing to its discrete nature. Two effective approaches for computing integer matrix factorization are proposed in this investigation---one is based on hamming distance and the other on Euclidean distance. A lower rank approximation of a matrix A ∈ Zmxn ≈ UV with factors U ∈ Zmxk2 , V ∈ Zkxn , where columns of U are mutually exclusive and integer k < min{m, n} is given. The third algorithm concerns expressing a nonnegative matrix as the shortest sum of nonnegative rank one matrices, the so called nonnegative rank factorization. Till now, only a few abstract results which are somewhat too conceptual for numerical implementation have been developed in the literature. Employing the Wedderburn rank reduction formula, a numerical procedure detecting whether a nonnegative rank factorization exists is presented. In the event that such a factorization does not exist, it is able to compute the maximum nonnegative rank splitting. (Abstract shortened by UMI.)...