Pascal Koiran

activity

20222026

collaborators

5 papers

cs.CC2026

Polynomial Bounds on Degeneration Order from Commutativity Properties of Tensor Slices

Shree Ganesh, Pascal Koiran, Rafael Oliveira

A tensor has border rank at most $r$ if it can be written as $T = lim_{ε \to 0} T (ε)$ where $T (ε)$ has rank at most $r$ for all sufficiently sm…

cs.DS2024

An efficient uniqueness theorem for overcomplete tensor decomposition

Pascal Koiran

We give a new, constructive uniqueness theorem for tensor decomposition. It applies to order 3 tensors of format $n \times n \times p$ and can prove uniqueness of decomposition for…

cs.DS2024

Undercomplete Decomposition of Symmetric Tensors in Linear Time, and Smoothed Analysis of the Condition Number

Pascal Koiran, Subhayan Saha

We study symmetric tensor decompositions, i.e., decompositions of the form $T = \sum_{i = 1}^{r} u_{i}^{\otimes 3}$ where $T$ is a symmetric tensor of order 3 and $u_{i} \in C^{n}$ .…

cs.DS2024

On the uniqueness and computation of commuting extensions

Pascal Koiran

A tuple (Z_1,...,Z_p) of matrices of size r is said to be a commuting extension of a tuple (A_1,...,A_p) of matrices of size n <r if the Z_i pairwise commute and each A_i sits in t…

cs.DS2022

Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision

Pascal Koiran, Subhayan Saha

We study symmetric tensor decompositions, i.e. decompositions of the input symmetric tensor T of order 3 as sum of r 3rd-order tensor powers of u_i where u_i are vectors in \C^n. I…