Computing symmetric nonnegative rank factorizations

被引：11

作者：

Kalofolias, V. ^{[1
]}

Gallopoulos, E. ^{[1
]}

机构：

[1] Univ Patras, Dept Comp Engn & Informat, GR-26110 Patras, Greece

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2012年 / 436卷 / 02期

关键词：

Nonnegative rank factorization; Nonnegative matrix factorization; Symmetric; Rotation; Isometry; Principal submatrix; Pivoted Cholesky factorization; Symmetric positive semidefinite; Arrowhead matrix; Extreme ray; Maximum independent set; Rank reduction; MATRIX FACTORIZATION; MODEL;

D O I：

10.1016/j.laa.2011.03.016

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

An algorithm is described for the nonnegative rank factorization (NRF) of some completely positive (CP) matrices whose rank is equal to their CP-rank. The algorithm can compute the symmetric NRF of any nonnegative symmetric rank-r matrix that contains a diagonal principal submatrix of that rank and size with leading cost O(rm(2)) operations in the dense case. The algorithm is based on geometric considerations and is easy to implement. The implications for matrix graphs are also discussed. (C) 2011 Elsevier Inc. All rights reserved.

引用

页码：421 / 435

页数：15

共 38 条

[1] A reverse Hadamard inequality [J].

Ambikkumar, S ;

Drury, SW .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1996, 247 :83-95

[2]

[Anonymous], 1959, THEORY MATRICES

[3]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[4]

Berman A., 2003, Completely positive matrices

[5] A note on the computation of the CP-rank [J].

Berman, Abraham ;

Rothblum, Uriel G. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2006, 419 (01) :1-7

[6]

Berman Abraham., 1974, Linear and Multilinear Algebra, V2, P161

[7]

Bermudez A. J., 1994, SAVMA Symposium 1994 Proceedings., P1

[8] The difference between 5 x 5 doubly nonnegative and completely positive matrices [J].

Burer, Samuel ;

Anstreicher, Kurt M. ;

Duer, Mirjam .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2009, 431 (09) :1539-1552

[9] On the copositive representation of binary and continuous nonconvex quadratic programs [J].

Burer, Samuel .

MATHEMATICAL PROGRAMMING, 2009, 120 (02) :479-495

[10] COMPUTING NONNEGATIVE RANK FACTORIZATIONS [J].

CAMPBELL, SL ;

POOLE, GD .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1981, 35 (FEB) :175-182

← 1 2 3 4 →