Parameterized Algorithms for the Matrix Completion Problem

被引：0

作者：

Ganian, Robert ^{[1
]}

Kanj, Iyad ^{[2
]}

Ordyniak, Sebastian ^{[3
]}

Szeider, Stefan ^{[1
]}

机构：

[1] TU Wien, Algorithms & Complex Grp, Vienna, Austria

[2] Depaul Univ, Sch Comp, Chicago, IL 60604 USA

[3] Univ Sheffield, Algorithms Grp, Sheffield, S Yorkshire, England

来源：

INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 80 | 2018年 / 80卷

关键词：

COMPLEXITY; GRAPHS;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We consider two matrix completion problems, in which we are given a matrix with missing entries and the task is to complete the matrix in a way that (1) minimizes the rank, or (2) minimizes the number of distinct rows. We study the parameterized complexity of the two aforementioned problems with respect to several parameters of interest, including the minimum number of matrix rows, columns, and rows plus columns needed to cover all missing entries. We obtain new algorithmic results showing that, for the bounded domain case, both problems are fixed-parameter tractable with respect to all aforementioned parameters. We complement these results with a lower-bound result for the unbounded domain case that rules out fixed-parameter tractability w.r.t. some of the parameters under consideration.

引用

页数：10

共 32 条

[11] Matrix Completion With Noise [J].

Candes, Emmanuel J. ;

Plan, Yaniv .

PROCEEDINGS OF THE IEEE, 2010, 98 (06) :925-936

[12] Exact Matrix Completion via Convex Optimization [J].

Candes, Emmanuel J. ;

Recht, Benjamin .

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2009, 9 (06) :717-772

[13] Partition into cliques for cubic graphs: Planar case, complexity and approximation [J].

Cerioli, M. R. ;

Faria, L. ;

Ferreira, T. O. ;

Martinhon, C. A. J. ;

Protti, F. ;

Reed, B. .

DISCRETE APPLIED MATHEMATICS, 2008, 156 (12) :2270-2278

[14]

Courtois N., 2002, Public Key Cryptography. 4th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002. Proceedings (Lecture Notes in Computer Science Vol.2274), P211

[15]

Downey Rodney G., 2013, Texts in Computer Science, DOI [DOI 10.1007/978-1-4471-5559-1, 10.1007/978-1-4471-5559-1]

[16] Sparse Subspace Clustering: Algorithm, Theory, and Applications [J].

Elhamifar, Ehsan ;

Vidal, Rene .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2013, 35 (11) :2765-2781

[17]

Endriss U, 2015, PROCEEDINGS OF THE 2015 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS (AAMAS'15), P127

[18] Fast Monte-Carlo algorithms for finding low-rank approximations [J].

Frieze, A ;

Kannan, R ;

Vempala, S .

JOURNAL OF THE ACM, 2004, 51 (06) :1025-1041

[19] The complexity landscape of decompositional parameters for ILP [J].

Ganian, Robert ;

Ordyniak, Sebastian .

ARTIFICIAL INTELLIGENCE, 2018, 257 :61-71

[20]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

← 1 2 3 4 →