1
$\begingroup$

Let $A$ be an $m\times n$ matrix with entries in $F$ ($F=\mathbb{R}$ or $F=\mathbb{C}$). It is well-known that $A$ has decompositions of the form $$\displaystyle A = \sum_{k=1}^r\lambda_k\hspace{2mm} x_k\otimes y_k$$ for some $r\in\mathbb{N}$ and $\lambda_k>0$, $x_k\in F^m$, $y_k\in F^n$, for example via SVD. Consider the problem $$\begin{array}{rl} \min & \sum_{k=1}^r \lambda_k \\ \textrm{subject to }1: & A = \sum_{k=1}^r \lambda_k \hspace{2mm} x_k\otimes y_k \\ 2: & \lambda_k>0 \\ 3: & -1\leq x_k \leq 1, \hspace{2mm} -1\leq y_k\leq 1 \hspace{15mm} (\textrm{if}\hspace{2mm}F=\mathbb{R})\\ 3':& |x_k| \leq 1, \hspace{2mm} |y_k|\leq 1 \hspace{15mm} (\textrm{if}\hspace{2mm}F=\mathbb{C})\\ \end{array}$$ Here $r$ can vary from one decomposition to another. It can be shown the solutions exist by a compactness argument.

Question: How can we algorithmically calculate a decomposition of $A$, which solves the minimization problem above? What's the speed of known (if any) algorithms as $m,n\to\infty$?

Edit (4/3/2022): The minimizer of $\sum_{k=1}^r \lambda_k$ above is in fact the projective tensor norm of $A$. One can calculate it by solving the easier unconstrained problem $$\max \{trace(BA): \|B\|_{\ell^m_{\infty}\to\ell^n_1}\leq 1\} $$ by duality. However, the emphasis here is on the decomposition(s) that can be obtained constructively or calculated by a fast algorithm.

Improve this question
$\endgroup$
3
  • $\begingroup$ A couple of remarks that fall short of an answer: (1) The value of the minimization problem that you've described is called the "projective tensor norm" of the $\ell^\infty$-norm (i.e., the norm given by $\|\mathbf{x}\|_{\infty} = \max_k\{|x_k|\}$). (2) The value of the minimum can be computed via semidefinite programming (in something like $O(m^3n^3)$ time). Decompositions themselves could be computed via the same techniques if we had a useful upper bound on $r$. $\endgroup$
    – Nathaniel Johnston
    Commented Feb 20, 2022 at 13:36
  • $\begingroup$ @NathanielJohnston thank you for your reply. I'm glad you brought the tensor norm on the table. If $X$, $Y$ are finite dimensional normed spaces, and $B_X$ & $B_Y$ & $B(X\hat{\otimes}_{\pi} Y)$ are the unit balls of the respective norms, then $B(X\hat{\otimes}_{\pi} Y)$ is the convex hull of $B_X\otimes B_Y$. Can we infer $r=mn$ or a multiple of $mn$? $\endgroup$
    – Onur Oktay
    Commented Feb 20, 2022 at 16:20
  • $\begingroup$ I'm also interested in decompositions where $\ell_\infty$ norm is replaced with $\ell_p$ norms for $p\notin\{1,2\}$. $\endgroup$
    – Onur Oktay
    Commented Feb 20, 2022 at 16:22

0

Reset to default

You must log in to answer this question.