Computing approximate PSD factorizations

Basu, Amitabh ; Dinitz, Michael ; et al.

2016

Online unknown

Zugriff:

We give an algorithm for computing approximate PSD factorizations of nonnegative matrices. The running time of the algorithm is polynomial in the dimensions of the input matrix, but exponential in the PSD rank and the approximation error. The main ingredient is an exact factorization algorithm when the rows and columns of the factors are constrained to lie in a general polyhedron. This strictly generalizes nonnegative matrix factorizations which can be captured by letting this polyhedron to be the nonnegative orthant.

10 pages

Titel:	Computing approximate PSD factorizations
Autor/in / Beteiligte Person:	Basu, Amitabh ; Dinitz, Michael ; Li, Xin
Link:	View record in OpenAIRE (Volltext) http://arxiv.org/abs/1602.07351
Veröffentlichung:	2016
Medientyp:	unknown
Schlagwort:	FOS: Computer and information sciences 000 Computer science, knowledge, general works MathematicsofComputing_NUMERICALANALYSIS 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Optimization and Control (math.OC) 010201 computation theory & mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Computer Science Computer Science - Data Structures and Algorithms FOS: Mathematics 0202 electrical engineering, electronic engineering, information engineering Data Structures and Algorithms (cs.DS) Mathematics - Optimization and Control MathematicsofComputing_DISCRETEMATHEMATICS
Sonstiges:	Nachgewiesen in: OpenAIRE Sprachen: English Language: English Rights: OPEN

Klicken Sie ein Format an und speichern Sie dann die Daten oder geben Sie eine Empfänger-Adresse ein und lassen Sie sich per Email zusenden.

BibTeX Citavi, JabRef, u.a.
(Literaturverwaltung)

PDF kein Volltext!
(Merkzettel, Notizen)

RIS Endnote, Citavi u.a.
(Literaturverwaltung)

MODS
(XML zur Weiterverarbeitung)

oder

Wählen Sie das für Sie passende Zitationsformat und kopieren Sie es dann in die Zwischenablage, lassen es sich per Mail zusenden oder speichern es als PDF-Datei.

Gewünschter Zitations-Stil:

oder

Bitte prüfen Sie, ob die Zitation formal korrekt ist, bevor Sie sie in einer Arbeit verwenden. Benutzen Sie gegebenenfalls den "Exportieren"-Dialog, wenn Sie ein Literaturverwaltungsprogramm verwenden und die Zitat-Angaben selbst formatieren wollen.