6
$\begingroup$

Let $f:[n]\times [n] \rightarrow [0,1]$ be a function from pair of integers to the real interval [0.1]. I would like to find sets of complex vectors $X= \{x_i\}$ and $Y=\{y_j\}$ satisfying $x_i\cdot y_j=f(i,j)$, in such a way that the vectors in $X$ and in $Y$ are as small as possible. More precisely, set $m= \max_{i,j} f(i,j)$ and $N=\max_{i,j}[\|x_i\|,\|y_j\|]$.

  1. What is the minimal $N$ such that $x_i\cdot y_j = f(i,j)$ for all $i,j\in [n]$?

  2. Is there an upper bound on $N$ purely in function of $m$, i.e., with no dependence on $n$?

  3. If the answer to question two is no, what is the best upper bound that we can give for $N$ in function of $n$ and $m$? A trivial upper bound is $$N \leq \max_i{\sum_{j} f(i,j) } \leq mn.$$

but I believe that the dependence on $n$ might be lowered.

cordially,

mateus

Improve this question
$\endgroup$
6
  • $\begingroup$ Why do you believe such vectors exist? $f(0,1)=f(1, 0)=1, f(0,0)=f(1, 1)=0$, for example. $\endgroup$
    – Daniel Litt
    Commented Jul 9, 2010 at 15:59
  • 2
    $\begingroup$ Daniel, I thought this was the snag at first, but I believe Mateus is asking for sequences of vectors $x_1,\ldots,y_1,\ldots$ such that $x_i\cdot y_j=f(i,j)$, that is in effect matrices $X$ and $Y$ with $XY^t=F$ (where $F$ is the function $f$ seen as a matrix). So in your example we can take $x_1=y_2=(1,0)$ and $x_2=y_1=(0,1)$. $\endgroup$
    – Robin Chapman
    Commented Jul 9, 2010 at 16:07
  • $\begingroup$ Ah I see; must have misread. $\endgroup$
    – Daniel Litt
    Commented Jul 9, 2010 at 16:11
  • $\begingroup$ Thanks Robin for clarifying Daniel's question. Thanks also Mike for your answer. Unfortunately an SDP doesn't help too much in here. I'm really interested in some analytical upper or lower bound on N. Even a non-constructive bound would be very welcome. $\endgroup$
    – Mateus de Oliveira
    Commented Jul 9, 2010 at 18:59
  • 3
    $\begingroup$ This question raises the notion of "factoring an operator through $\ell_2$." You may want to consider references on the Pietsch factorization theorem and Grothendiek's inequality. $\endgroup$
    – Mike McCoy
    Commented Jul 9, 2010 at 19:55

2 Answers 2

Reset to default
10
$\begingroup$

Such questions have been dealt with. Note first that your $m$ is just the norm of the matrix $F$ (see Robin's comment) as an operator from $\ell_1^n$ to $\ell_\infty^n$. $M$ also has a name, it is the $\gamma_2$ norm of this operator (This is the minimal product of $$\|Y\|_{1\to 2}\|X\|_{2\to\infty}$$ over all factorizations $F=XY$ . $\|Z\|_{p\to q}$ denotes the norm of Z as an operator from $\ell_p$ to $\ell_q$.) It is not hard to see that $M=\gamma_2(F)\le \sqrt n \|F\|_{1\to\infty}=\sqrt n m$. For a random $0,1$ matrix $F$ one gets that this estimate is tight, up to a universal constant. You can look here Link for details. In particular Cor 5.2 there (it deals with random $\pm 1$ matrices but it is easy to go between those and random $0,1$ matrices).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Back ticks are what you need around some math expressions to make them display correctly, Gideon, so I changed your single quotes to back ticks. $\endgroup$
    – Bill Johnson
    Commented Jul 9, 2010 at 23:11
  • $\begingroup$ Hi Gideon, thank you very much for your comment, and for pointing out the reference which I partially read and found very interesting. However I might be missing something. Your $M$ (which I call $N$) seems to be $\min_{XY}\{max_{ij}\|x_i\| \|y_j\|\}$. However in the question I made, the maximum is not over the product of the norms $\|x_i\|\|y_j\|$. Instead in the def. of $N$, I consider the largest line of $X$ and the largest column of $Y$, and take the largest between the two. More precisely, I should have written $\max\{\max_i{x_i}; \max_j{y_j}\}$. Any clue? $\endgroup$
    – Mateus de Oliveira
    Commented Jul 10, 2010 at 0:52
  • 1
    $\begingroup$ Mateus, you are right but it is easy to go between my $M$ and your $N$ (for the minimal representation). $M=N^2$. (Note that for the $i,j$ for which the max is attained in $N$ one has $\|x_i\|=\|y_j\|$). So $N= M^{1/2}\le n^{1/4}m^{1/2}$. and the random example shows that this is best possible, up to a universal constant. I hope it's OK now. $\endgroup$
    – Gideon Schechtman
    Commented Jul 10, 2010 at 4:44
  • $\begingroup$ Thank you very much Gideon for the great answer! It will help me a lot in proving a lemma in which I was stuck. $\endgroup$
    – Mateus de Oliveira
    Commented Jul 10, 2010 at 15:54
0
$\begingroup$

This is a partial answer; I'm not sure it will be useful to you. I don't see any analytic expression for (1), but if we restrict ourselves to real vectors and the Euclidean norm, you can compute $N$ using a semidefinite program. Consider the problem

$$\text{minimize } \max_{i,j} \{(W_1)_{ii}, (W_2)_{jj}\} \quad \text{subject to } \begin{bmatrix}W_1& F \newline F' & W_2 \end{bmatrix} \succeq 0, $$

where as in Robin's comment, $F$ is the matrix version of $f$. To compute $x_i$, $y_j$ after finding the optimal matrices $W_1, W_2$, one simply needs to take the Cholesky factorization

$$ \begin{bmatrix} X \newline Y \end{bmatrix} \begin{bmatrix} X^t & Y^t \end{bmatrix} = \begin{bmatrix}W_1& F \newline F' & W_2 \end{bmatrix}, $$

and take the corresponding rows of $X$ and $Y$ as your vectors $x_i, y_j$. Note that the optimal value of this program is $N^2$ (when restricted to real vectors). It is also trivially an upper bound on $N^2$ when considering complex vectors.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .