\pmatrix{\widetilde{{\mbox{\boldmath $g$}}}_n^{(\ell)} \cr \widetilde{g}_{n+1}^{(\ell)}}:=g_1 L_{n+1}^{(\ell)}{\mbox{\boldmath $e$}}_1. \nonumber\end{aligned}$$ From the above least squares problems we readily see that ${\mbox{\boldmath $y$}}_n^{(\ell)}=\ \bigr(B_n^{(\ell)}\bigl)^{-1}\widetilde{{\mbox{\boldmath $g$}}}_n^{(\ell)}$. Hence it follows from (\[sol\]) and using $(\widetilde{{\mbox{\boldmath $p$}}}_1\ \widetilde{{\mbox{\boldmath $p$}}}_2\ \cdots\ \widetilde{{\mbox{\boldmath $p$}}}_n):=V_n(B_n^{(\ell)})^{-1}$ that we have the following coupled two-term recurrence relations: $$\begin{aligned}
 \widetilde{{\mbox{\boldmath $p$}}}_{n}^{(\ell)}&=& ({\mbox{\boldmath $v$}}_{n}-t_{n-1,n}^{(\ell)}\widetilde{{\mbox{\boldmath $p$}}}_{n-1}^{(\ell)})/t_{n,n}^{(\ell)},   \label{x_rec1_B}\\
 {\mbox{\boldmath $x$}}_{n}^{(\ell)}&=&{\mbox{\boldmath $x$}}_{n-1}^{(\ell)}+\widetilde{g}_n^{(\ell)}\widetilde{{\mbox{\boldmath $p$}}}_n^{(\ell)}. \label{x_rec2_B}\end{aligned}$$ The cost per iteration is now $5Nm$. Substituting ${\mbox{\boldmath $p$}}_i^{(\ell)}=t_{i,i}^{(\ell)}\widetilde{{\mbox{\boldmath $p$}}}_i^{(\ell)}$ into the above recurrences, we have the even more efficient recurrence formulas. $$\begin{aligned}
 {\mbox{\boldmath $p$}}_{n}^{(\ell)}&=& {\mbox{\boldmath $v$}}_{n}-(t_{n-1,n}^{(\ell)}/t_{n-1,n-1}^{(\ell)}){\mbox{\boldmath $p$}}_{n-1}^{(\ell)}, \\
 {\mbox{\boldmath $x$}}_{n}^{(\ell)}&=&{\mbox{\boldmath $x$}}_{n-1}^{(\ell)}+(\widetilde{g}_n^{(\ell)}/t_{n,n}^{(\ell)}){\mbox{\boldmath $p$}}_n^{(\ell)}.\end{aligned}$$ By this reformulation, the cost becomes $4Nm+2m$.

Next, let us consider a choice for $L_{n+1}^{(\ell)}$ satisfying (\[bidiagonal\_weight\]). Let $F_{n}^{(\ell)}$ be an $n$-by-$n$ matrix for the form $$\begin{aligned}
  F_n^{(\ell)}(i):= 
  \pmatrix{
    I_{i-1}  &           &     & \cr
             &      1    &     & \cr
             &  f_{i}^{(\ell)}&   1 & \cr
             &           &     & I_{n-i-1}        
  },    \label{F}\end{aligned}$$ and let $T$ be tridiagonal. Then, by determining $f_i^{(\ell)}$ such that the $(i+1,i)$ entry of the matrix $F_n^{(\ell)}(i)T$ is zero, we can fulfill (\[bidiagonal\_weight\]) in the following way: $$\begin{aligned}
  F_{n+1}^{(\ell)}(n)F_{n+1}^{(\ell)}(n-1)\cdots F_{n+1}^{(\ell)}(1)T_{n+1,n}^{(\ell)}=
\pmatrix{
         B_n^{(\ell)} \cr
         \mathbf{0}^{\textrm{\scriptsize{T}}}\cr 
         }  \label{FN}.      \end{aligned}$$ From the above we see that $F_{n+1}^{(\ell)}(n)F_{n+1}^{(\ell)}(n-1)\cdots F_{n+1}^{(\ell)}(1)=L_{n+1}^{(\ell)}$, and thus $L_{n+1}^{(\ell)}$ and $L_{n}^{(\ell)}$ are related by $$\begin{aligned}
  L_{n+1}^{(\ell)} = F_{n+1}^{(\ell)}(n)\pmatrix{
         L_n^{(\ell)} & 