$\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$.)

6more comments