You are here

Matrix Completion for the Independence Model

Journal Name:

Publication Year:

Abstract (2. Language): 
We investigate the problem of completing partial matrices to rank-one matrices in the standard simplex mn1. The motivation for studying this problem comes from statistics: A lack of eligible completion can provide a falsi cation test for partial observations to come from the independence model. For each pattern of speci ed entries, we give equations and inequalities which are satis ed if and only if an eligible completion exists. We also describe the set of valid completions, and we optimize over this set.
1
21

JEL Codes:

REFERENCES

References: 

[1] Saugata Basu, Richard Pollack, and Marie-Francoise Roy. Algorithms in real alge-
braic geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-
Verlag, Berlin, second edition, 2006.
[2] Emmanuel J. Candes and Benjamin Recht. Exact matrix completion via convex
optimization. Found. Comput. Math., 9(6):717{772, 2009.
[3] Emmanuel J. Candes and Terence Tao. The power of convex relaxation: Near-optimal
matrix completion. IEEE Trans. Inf. Theor., 56(5):2053{2080, 2010.
[4] Nir Cohen, Charles R. Johnson, Leiba Rodman, and Hugo J. Woerdeman. Ranks of
completions of partial matrices. In The Gohberg anniversary collection, Vol. I (Cal-
gary, AB, 1988), volume 40 of Oper. Theory Adv. Appl., pages 165{185. Birkhauser,
Basel, 1989.
[5] Maryam Fazel, Haitham Hindi, and Stephen P. Boyd. A rank minimization heuristic
with application to minimum order system approximation. In Proceedings of the 2001
American Control Conference, volume 6, pages 4734{4739. IEEE, 2001.
[6] Don Hadwin, K. J. Harrison, and Josephine A.Ward. Rank-one completions of partial
matrices and completely rank-nonincreasing linear functionals. Proc. Amer. Math.
Soc., 134(8):2169{2178, 2006.
[7] Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion
from a few entries. IEEE Trans. Inf. Theor., 56(6):2980{2998, 2010.
[8] Gary King. A Solution to the Ecological Inference Problem: Reconstructing Individual
Behavior from Aggregate Data. Princeton University Press, Princeton, 1997.
[9] Franz J. Kiraly and Louis Theran. Error-minimizing estimates and universal entrywise
error bounds for low-rank matrix completion. In C.J.C. Burges, L. Bottou,
M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural In-
formation Processing Systems 26, pages 2364{2372. Curran Associates, Inc., 2013.
REFERENCES 21
[10] Franz J Kiraly, Louis Theran, and Ryota Tomioka. The algebraic combinatorial
approach for low-rank matrix completion. J. Mach. Learn. Res., 16:1391{1436, 2015.
[11] Kaie Kubjas, Elina Robeva, and Bernd Sturmfels. Fixed points of the EM algorithm
and nonnegative rank boundaries. Ann. Statist., 43(1):422{461, 2015.
[12] Joseph M. Landsberg. Tensors: geometry and applications, volume 128 of Graduate
Studies in Mathematics. American Mathematical Society, Providence, RI, 2012.
[13] Jiawang Nie, Pablo A. Parrilo, and Bernd Sturmfels. Semidenite representation of
the k-ellipse. In Alicia Dickenstein, Frank-Olaf Schreyer, and Andrew J. Sommese,
editors, Algorithms in Algebraic Geometry, volume 146 of The IMA Volumes in Math-
ematics and its Applications, pages 117{132. Springer, New York, 2008.
[14] Benjamin Recht. A simpler approach to matrix completion. J. Mach. Learn. Res.,
12:3413{3430, 2011.
[15] Bernd Sturmfels and Caroline Uhler. Multivariate gaussians, semidenite matrix
completion, and convex algebraic geometry. Ann. Inst. Stat. Math., 62(4):603{638,
2010.

Thank you for copying data from http://www.arastirmax.com