Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: linear programming

Sortuj według:

Ogranicz wyniki do:

A linear programming based analysis of the CP-rank of completely positive matrices

100%

Li Y., Kummert A., Frommer A.

International Journal of Applied Mathematics and Computer Science

2004

tom 14

nr 1

25-31

A real matrix A is said to be completely positive (CP) if it can be decomposed as A = BB^T, where the real matrix B has exclusively non-negative entries. Let k be the rank of A and Φ_k the least possible number of columns of the matrix B, the so-called completely positive rank (cp-rank) of A. The present work is devoted to a study of a general upper bound for the cp-rank of an arbitrary completely positive matrix A and its dependence on the ordinary rank k. This general upper bound of the cp-rank has been proved to be at most k(k + 1)/2. In a recent pioneering work of Barioli and Berman it was slightly reduced by one, which means that Φ_k ≤ k(k + 1)/2 - 1 holds for k ≥ 2. An alternative constructive proof of the same result is given in the present paper based on the properties of the simplex algorithm known from linear programming. Our proof illuminates complete positivity from a different point of view. Discussions concerning dual cones are not needed here. In addition to that, the proof is of constructive nature, i.e. starting from an arbitrary decomposition A = B_1B^T_1 (B_1 ≥ 0) a new decomposition A = B_2B^T_2 (B_2 ≥ 0) can be generated in a constructive manner, where the number of column vectors of B_2 does not exceed k(k + 1)/2 − 1. This algorithm is based mainly on the well-known techniques stemming from linear programming, where the pivot step of the simplex algorithm plays a key role.

Ograniczanie wyników

1 International Journal of Applied Mathematics and Computer Science

1 Frommer A.

1 Kummert A.

1 Li Y.

1 2004

Wyniki wyszukiwania

A linear programming based analysis of the CP-rank of completely positive matrices