8
$\begingroup$

Suppose that $1 < k < n$. Does there exist a constant $\beta > 0$, such that for every $k$ orthonormal vectors $f_1,\ldots,f_k \in \mathbb R^n$, there exist $k$ orthonormal vectors with nonnegative elements, $x_1,\ldots,x_k\in \mathbb R_+^n$, such that

$$\sum_{i=1}^k \|x_i - f_i\|^2_2 \leq \beta \sum_{i=1}^k\|f_i^-\|_2^2$$

where $f_i^- := \max\{-f_i,0\}$ is the negative part of the vectors $f_i$?


In another way, I am interested in the estimation of the distance of a $n\times k$ dimensional matrix $F$ whose columns are orthonormal from the set of $n\times k$ matrices whose columns are nonnegative and orthonormal, i.e.,

$$ \mathrm{dist}(F;St_+(n,k)) $$

Where $St_+(n,k)$ is the set of $n\times k$ matrices whose columns are nonnegative and orthonormal. If we drop orthonormal condition and compute $\mathrm{dist}(F;\mathbb{R}^{n\times k }_+)$, we obtain $\|F^-\|$ as a lower bound for the above distance. In this term, my question is as follows: Is a multiple of $\|F^-\|$ an upper bound for the above distance, i.e.,

Is there a constant $c>0$, such that $$ \|F^-\| \leq \mathrm{dist}(F;St_+(n,k)) \leq c \|F^-\| $$ for every $n\times k$ dimentional matrix $F$ whose columns are orthonormal?

In the special case $k=1$, the above statement is true, with $c = 2$. I'm interested in the special case of small values of $k$, such as $k=2$. Experimentally, for $k>1$ and random matrices $F$ and by using Frobenius norm, I get an upper bound for $\mathrm{dist}(F; St_+(n,k))$ by alternating projection to nonnegative matrices and orthonormal matrices. I guess that the above statement is true for $c \approx 2$, $(\beta \approx 4)$.

$\endgroup$
11
  • $\begingroup$ This looks like a combinatorial problem. Indeed, for any $k>1$, there are only finitely many possible choices for $x_1,\ldots,x_k$. $\endgroup$
    – Surb
    Apr 15, 2018 at 10:51
  • $\begingroup$ @Mahdi What do you know? What have you tried? Also, it looks related your Steifel manifold question from earlier. Some background would be welcome. $\endgroup$
    – Boris Bukh
    Apr 15, 2018 at 11:49
  • 4
    $\begingroup$ What are you going to do with $(1,\sqrt{2\varepsilon},-\varepsilon)$ and $(-\varepsilon,\sqrt{2\varepsilon},1)$? $\endgroup$
    – fedja
    Apr 15, 2018 at 19:19
  • 2
    $\begingroup$ I think that it may work if you drop the squares on the right hand side. It definitely gives you the right scaling and if you don't care too much about the dependence of $\beta$ on $k$, it gets trivial with $\beta=k$ then. However, I still want to see if we can get a neat inequality before posting anything. Also, will such an estimate (if true) suffice for your purposes? $\endgroup$
    – fedja
    Apr 15, 2018 at 21:26
  • 1
    $\begingroup$ No, that one is fine: approximate by $(1,0,\varepsilon^{2/3},0)$ and $(0,1,0,\varepsilon^{1/4})$. Then $LHS=\varepsilon^{3/2}$ and $RHS=\varepsilon^{2/3}$ (without squares). I'll post the bound a bit later $\endgroup$
    – fedja
    Apr 16, 2018 at 17:01

1 Answer 1

3
$\begingroup$

$\newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\PP}{\operatorname{\mathsf P}} \newcommand{\ii}[1]{\operatorname{\mathsf I}\{#1\}}$

The following two simple lemmas are crucial.

Lemma 1. For any nonnegative numbers $a_1,\dots,a_k$, \begin{equation*} \sum_1^k a_i^2-\max_1^ka_i^2\le\sum_{1\le i<i'\le k}a_i a_{i'}. \end{equation*}

Proof. Without loss of generality, $a_1=\max_1^ka_i$. Then $a_i^2\le a_1a_i$ for all $i=2,\dots,k$. So, Lemma 1 follows.

For any $u\in\R^n$, let $u^+ :=\max\{u,0\}$ and $u^- :=\max\{-u,0\}$, so that $u=u^+-u^-$.

Lemma 2. For any orthonormal vectors $u$ and $v$, \begin{equation*} u^+\cdot v^+\le \|u^-\|+\|v^-\|, \end{equation*} where $\cdot$ denotes the dot product.

Proof. We have $0=u\cdot v=u^+\cdot v^+ - u^+\cdot v^- -u^-\cdot v^+ + u^-\cdot v^- \ge u^+\cdot v^+ - \|u^+\|\,\|v^-\| -\|u^-\|\,\| v^+\|$, whence Lemma 2 follows.

As in the question, let now $f_1,\ldots,f_k$ be any orthonormal vectors in $\R^n$. Write $f_i=(f_{ij})_{j=1}^n$ and $f^+_i=(f^+_{ij})_{j=1}^n$. Let $(J_1,\dots,J_k)$ be any partition of the set $[n]:=\{1,\dots,n\}$ such that for all $i\in[k]$ and $j\in[n]$ we have the implication \begin{equation*} j\in J_i\implies f^+_{ij}=\max_{q\in[k]}f^+_{qj}. \end{equation*} Define $y_i=(y_{ij})_{j=1}^n$ by \begin{equation*} y_{ij}:=f^+_{ij}\,\ii{j\in J_i}, \end{equation*} where $\ii{}$ denotes the indicator; so, $y_{ij}=\max_{q\in[k]}f^+_{qj}$ for $j\in J_i$ and $y_{ij}=0$ for $j\in[n]\setminus J_i$. Hence, in view of Lemmas 1 and 2, \begin{multline*} \sum_1^k\|y_i-f^+_i\|^2 =\sum_{j\in[n]}\Big(\sum_{i\in[k]}(f^+_{ij})^2-\max_{i\in[k]}(f^+_{ij})^2\Big) \le\sum_j\sum_{i<i'}f^+_{ij}f^+_{i'j} \\ =\sum_{i<i'}f^+_i\cdot f^+_{i'} \le\sum_{i<i'}(\|f^-_i\|+\|f^-_{i'}\|) =2(k-1)\sum_{i\in[k]}\|f^-_i\|. \tag{1} \end{multline*}

Also, $\sum_1^k\|f_i-f^+_i\|^2=\sum_1^k\|f^-_i\|^2\le\sum_1^k\|f^-_i\|$. So, by (1) and Minkowski's inequality,
\begin{equation*} \sum_{i\in[k]}\|y_i-f_i\|^2 \le(\sqrt{2(k-1)}+1)^2\sum_{i\in[k]}\|f^-_i\|\le3k\sum_{i\in[k]}\|f^-_i\|=:\ep. \tag{2} \end{equation*}

Next, \begin{equation} 0\le1-\|y_i\|=\|f_i\|-\|y_i\|\le\|y_i-f_i\|, \tag{3} \end{equation} by the triangle inequality.

Consider now two possible cases:

Case 1: $\ep<1$. (This is hopefully the main case.) Then, by (2), $\|y_i-f_i\|<1$ for all $i$, whence, by (3), $y_i\ne0$ for all $i$, so that we can let
\begin{equation*} x_i:=y_i/\|y_i\|. \end{equation*}

Then $x_1,\dots,x_k$ are orthonormal vectors in $\R_+^n$, and
\begin{equation*} \sum_{i\in[k]}\|x_i-y_i\|^2=\sum_{i\in[k]}(1-\|y_i\|)^2\le\sum_{i\in[k]}\|y_i-f_i\|^2\le\ep \end{equation*} by (3) and (2), which yields \begin{equation*} \sum_{i\in[k]}\|x_i-f_i\|^2 \le4\ep=12k\sum_{i\in[k]}\|f^-_i\|. \end{equation*}

Case 2: $\ep\ge1$. Here for any orthonormal $x_1,\dots,x_k$ we have \begin{equation*} \sum_{i\in[k]}\|x_i-f_i\|^2\le 2\sum_{i\in[k]}(\|x_i\|^2+\|f_i\|^2)=4k\le4k\ep =12k^2\sum_{i\in[k]}\|f^-_i\|. \end{equation*}

Thus, \begin{equation*} \sum_{i\in[k]}\|x_i-f_i\|^2\le \left\{ \begin{aligned} 12k\sum_{i\in[k]}\|f^-_i\|&\text{ if }\ep<1,\\ 12k^2\sum_{i\in[k]}\|f^-_i\|&\text{ if }\ep\ge1. \end{aligned} \right. \end{equation*}

(As follows from the comment by user fedja, here $\|f^-_i\|$ cannot be replaced by $\|f^-_i\|^{1+\ep}$, for any real $\ep>0$.)

$\endgroup$
3
  • $\begingroup$ It is possible that $y_i=0$, for example in the case that one of the $f_i$ has no positive elements. Also, why did you suppose that $\epsilon < 1$? $\endgroup$
    – Mahdi
    Apr 17, 2018 at 15:32
  • $\begingroup$ Thank you so much if you explain more why $\sum_{i\in[k]}(1-\|y_i\|^2)\le\sum_{i\in[k]}\|y_i-f_i\|^2$ in the 4th line from the end of your answer. $\endgroup$
    – Mahdi
    Apr 17, 2018 at 16:56
  • $\begingroup$ Thank you for your comments. I have now considered the case $\varepsilon\ge1$ as well. Also, I have added details showing that $y_i\ne0$ if $\varepsilon<1$. Concerning $(1-\|y_i\|^2)$, that was a typo: there should be (and now is) $(1-\|y_i\|)^2$ there instead. $\endgroup$ Apr 17, 2018 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.