Timezone: »

 
Poster
Deterministic Symmetric Positive Semidefinite Matrix Completion
William E Bishop · Byron M Yu

Wed Dec 10 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session »

We consider the problem of recovering a symmetric, positive semidefinite (SPSD) matrix from a subset of its entries, possibly corrupted by noise. In contrast to previous matrix recovery work, we drop the assumption of a random sampling of entries in favor of a deterministic sampling of principal submatrices of the matrix. We develop a set of sufficient conditions for the recovery of a SPSD matrix from a set of its principal submatrices, present necessity results based on this set of conditions and develop an algorithm that can exactly recover a matrix when these conditions are met. The proposed algorithm is naturally generalized to the problem of noisy matrix recovery, and we provide a worst-case bound on reconstruction error for this scenario. Finally, we demonstrate the algorithm's utility on noiseless and noisy simulated datasets.

[ PDF] 

Author Information

William E Bishop (Carnegie Mellon)
Byron M Yu (Carnegie Mellon University)

More from the Same Authors