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$
  • $\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 '18 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 '18 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 '18 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 '18 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 '18 at 17:01
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$
  • $\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 '18 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 '18 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$ – Iosif Pinelis Apr 17 '18 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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