Bounds for Matrix Factorization Ranks via Semidefinite Programming and...

on YouTube ↗32m

" summary

An SDP hierarchy gives computable lower bounds for nonnegative, PSD, CP and CPSD factorization ranks by encoding Gram factorizations as evaluations of polynomials on matrix or operator variables and minimizing the unnormalized trace. The method uses commutative and noncommutative polynomial optimization, moment matrices with flatness/Archimedean conditions for convergence, and extra localization or tensor constraints to strengthen CP/NN bounds. Numerical tests certify that low-order relaxations already separate nonnegative rank 3 from 4 on a nested-rectangle family and detect PSD-rank thresholds on a 3×3 circulant example.

AI-written summary · about

" chapters (8)

1. 0:00Matrix factorization ranks introduction
2. 3:11Four key factorization ranks
3. 8:07Known rank bounds
4. 12:13Polynomial optimization for bounds
5. 17:27SDP for lower rank bounds
6. 23:41Universal factorization rank approach
7. 27:10Bound comparisons with examples
8. 29:55Q&A