• PDF / 34,473,552 Bytes
• 360 Pages / 594 x 828 pts Page_size
• 79 Downloads / 202 Views

DOWNLOAD

REPORT

---

some matrix B. A matrix A is said to be completely positive if A - B B T for some nonnegative matrix B. An n x n real symmetric matrix D - (dij) is a Euclidean distance matrix (abbreviated as distance matrix) if there exist vectors vl,...', vn C R k (for some k > 1) such that, for all i, j - 1 , . . . , n, dij is equal to the square of the Euclidean distance between vi and vj. Finally, a (rectangular) matrix A is a contraction matrix if all its singular values (that is, the eigenvalues of A ' A ) are less than or equal to 1. The set of positions corresponding to the specified entries of a partial matrix A is known as the pattern of A. If A is an n x m partial matrix, its pattern can be represented by a bipartite graph with node bipartition [1, n] U [1, m] having an edge between nodes i e [1, n] and j e [1, m] if and only if entry aij is specified. When asking about existence of a psd completion of a partial n x n matrix A, it is commonly assumed that all diagonal entries of A are specified (which is no loss of generality if we ask for a pd completion); moreover, it can obviously be assumed that A is partial Hermitian, which means that entry aji is specified and equal to hi*j whenever aij is specified. Hence, in this case, complete information about the pattern of A is given by the graph G - ([1, n ] , E ) w i t h node set [1, n] and whose edge set E consists of the pairs ij (1 _ i < j _ n) for which aij is a specified entry of A. The same holds when dealing with distance matrix completions (in which case diagonal entries can obviously be assumed to be equal to zero). An important common feature of the above matrix properties is that they possess an 'inheritance

Matrix completion problems structure'. Indeed, if a partial matrix A has a psd (pd, completely positive, distance matrix) completion, then every principal specified submatrix of A is psd (pd, completely positive, a distance matrix); similarly, if a partial matrix A admits a completion of rank _ k, then every specified submatrix of A has rank < k. Hence, having a completion of a certain kind imposes certain 'obvious' necessary conditions. This leads to asking which are the patterns for the specified entries that insure that if the obvious necessary conditions are met, then there will be a completion of the desired type; therefore, this introduces a combinatorial aspect into matrix completion problems, as opposed to their analytical nature. In this article we survey some results and provide references for the various matrix completion problems mentioned above, concerning optimization and combinatorial aspects of the problems. See [32], [47] for more detailed surveys on some of the topics treated here. Positive Semidefinite Completion Problem. We consider here the following positive (semi) definite completion problem (PSD)" Given a partial Hermitian matrix A - (aij)ijES whose entries are specified on a subset S of the positions, determine whether A has a psd (or pd) completion; if, yes, find such a completion. (Here, S is generally assumed to contain all diag