分位点回帰

条件を満たす $(b,u,v)$ では $u_i-v_i=r_i(b)$ である。$u_i,v_i\ge0$ なので $u_i\ge r_i(b)^+$、$v_i\ge r_i(b)^-$（$c^+:=\max(c,0)$、$c^-:=\max(-c,0)$）であり、$\tau u_i+(1-\tau)v_i\ge\tau r_i(b)^++(1-\tau)r_i(b)^-=\rho_\tau(r_i(b))$ である。等号は $u_i=r_i(b)^+$、$v_i=r_i(b)^-$ で成り立ち、これは条件を満たす。よって、$b$ を固定したときの目的関数の最小値は $R_\tau(b)$ であり、2 つの主張が従う。$\square$

$I:=\{i\mid x_i^{\mathsf T}d\ne0\}$ とおく。$X$ の階数が $p$ なので $Xd\ne0$ であり、$I$ は空でない。$i\in Z(b)$ なら $x_i^{\mathsf T}d=0$ なので $I\cap Z(b)=\emptyset$ である。$i\in I$ の残差 $r_i(b+td)=r_i(b)-t\,x_i^{\mathsf T}d$ は $t$ の 1 次関数で、$t_i:=r_i(b)/x_i^{\mathsf T}d\ne0$ でだけ $0$ になる。$i\notin I$ の残差は $t$ によらない。$T_+:=\min\{t_i\mid t_i>0\}$、$T_-:=\max\{t_i\mid t_i< 0\}$ とおき（該当がなければ $\infty$、$-\infty$）、$J:=[T_-,T_+]\cap\mathbb R$ とする。$I\ne\emptyset$ なので少なくとも一方は有限である。
$J$ の内部では $i\in I$ の残差の符号が変わらないので、$\rho_\tau(r_i(b+td))$ は $t$ の 1 次関数であり、連続性から $J$ 全体で 1 次関数である。よって $\varphi$ は $J$ の上で 1 次関数 $\varphi(t)=\varphi(0)+ct$ である。
1：$T_+=\infty$ なら、$\varphi\ge0$ が $[0,\infty)$ で成り立つので $c\ge0$ であり、有限な $t^*:=T_-< 0$ で $\varphi(t^*)\le\varphi(0)$ である。$T_-=-\infty$ なら同様に $c\le0$ で $t^*:=T_+$ とする。両方有限なら、$c\ge0$ なら $t^*:=T_-$、$c< 0$ なら $t^*:=T_+$ とする。$t^*=t_j$ となる $j\in I$ をとると $r_j(b')=0$ である。$i\in Z(b)$ は $x_i^{\mathsf T}d=0$ なので $r_i(b')=0$ のままであり、$Z(b')\supset Z(b)\cup\{j\}$ である。$x_j^{\mathsf T}d\ne0$ だが $V(b)$ の元はすべて $d$ と直交するので $x_j\notin V(b)$ であり、$\dim V(b')>\dim V(b)$ である。
2：$T_-< 0< T_+$ なので $0$ は $J$ の内部にある。内部の点で最小値をとる 1 次関数は定数である。$\square$

1：$b$ から始めて lem-qr-step の 1 を繰り返すと、$R_\tau$ の値は増えず、$\dim V$ は毎回増えるので、高々 $p$ 回で $\dim V(b'')=p$ となる $b''$ に達する。$x_i$（$i\in Z(b'')$）から 1 次独立な $p$ 個を選び、その添字の集合を $h$ とすると $X_h$ は正則で、$X_hb''=y_h$ なので $b''=b(h)$ であり、$R_\tau(b(h))\le R_\tau(b)$ である。
2：基本解は有限個で、少なくとも 1 つある。その中で $R_\tau$ が最小のものを $b(h_0)$ とすると、1 によりすべての $b$ で $R_\tau(b(h_0))\le R_\tau(b)$ なので、$b(h_0)$ は最小点である。$\rho_\tau$ は凸関数で、$b\mapsto y_i-x_i^{\mathsf T}b$ は 1 次なので $R_\tau$ は凸であり、$S$ は凸集合である。$R_\tau$ は連続なので $S$ は閉集合である。有界性を示す。$m:=\min(\tau,1-\tau)>0$ とすると $\rho_\tau(u)\ge m\lvert u\rvert$ であり、$\| w\|_1:=\sum_i\lvert w_i\rvert$ として
$$ R_\tau(b)\ge m\| y-Xb\|_1\ge m\bigl(\| Xb\|_1-\| y\|_1\bigr) $$
である。$X$ の階数が $p$ なので $b\mapsto\| Xb\|_1$ は $\mathbb R^p$ のノルムで、単位球面（有界閉集合）の上の正の最小値 $c>0$ をもち、$\| Xb\|_1\ge c\lvert b\rvert$ である。よって $\lvert b\rvert$ が大きいと $R_\tau(b)>R_\tau(b(h_0))$ となり、$S$ は有界である。
3：$S$ が 2 点以上を含むとする。$S$ の点のうち辞書式順序（第 1 成分が最大のものの中で第 2 成分が最大、…）で最大の点 $e$ と最小の点 $e'$ は、$S$ が有界閉集合なのでとれて、互いに異なる。$e$ が基本解であることを示す（$e'$ も同様）。$\dim V(e)< p$ なら、lem-qr-step の 2 により、小さい $\varepsilon>0$ で $e\pm\varepsilon d\in S$ である。$e+\varepsilon d$ と $e-\varepsilon d$ の一方は辞書式順序で $e$ より大きいので、$e$ の選び方に反する。よって $\dim V(e)=p$ であり、1 の証明と同様に $e$ は基本解である。$\square$

$e_1:=(1,0,\dots,0)^{\mathsf T}$ とし、$\varphi(t):=R_\tau(b+te_1)$ とおく。切片の列があるので $r_i(b+te_1)=r_i(b)-t$ である。$\delta:=\min\{\lvert r_i(b)\rvert\mid r_i(b)\ne0\}$（$N^0=n$ なら $\delta:=1$）とし、$0< t< \delta$ とする。
$t>0$ の向き：$r_i(b)>0$ の項は $\tau(r_i(b)-t)$ で $\tau t$ だけ減り、$r_i(b)< 0$ の項は $(\tau-1)(r_i(b)-t)$ で $(1-\tau)t$ だけ増え、$r_i(b)=0$ の項は $\rho_\tau(-t)=(1-\tau)t$ になる。よって
$$ \varphi(t)-\varphi(0)=t\bigl(-\tau N^++(1-\tau)(N^-+N^0)\bigr)=t\bigl(N^-+N^0-n\tau\bigr) $$
である。$b$ は最小点なので左辺は $0$ 以上であり、$n\tau\le N^-+N^0$ を得る。
$-t$ の向き：同様に $r_i(b)>0$ の項は $\tau t$ 増え、$r_i(b)< 0$ の項は $(1-\tau)t$ 減り、$r_i(b)=0$ の項は $\rho_\tau(t)=\tau t$ になるので
$$ \varphi(-t)-\varphi(0)=t\bigl(\tau N^+-(1-\tau)N^-+\tau N^0\bigr)=t\bigl(n\tau-N^-\bigr) $$
であり、$N^-\le n\tau$ を得る。後半は $N^+=n-N^--N^0$ を代入すればよい。$\square$

要点：$\rho_\tau(\lambda u)=\lambda\rho_\tau(u)$（$\lambda>0$）と $\rho_{1-\tau}(-u)=\rho_\tau(u)$ から、目的関数がそれぞれ $R_\tau(b/\lambda)$ の $\lambda$ 倍、$R_\tau(-b)$、$R_\tau(b-\gamma)$、$R_\tau(Ab)$ に等しいことによる。

$\pi_j:=P(X=c_j)>0$ とし、$P_j(A):=P(A\cap\{X=c_j\})/\pi_j$ とおくと、$P_j$ は確率測度であり、$P_j$ のもとで $Y$ は可積分である（$E_j\lvert Y\rvert\le E\lvert Y\rvert/\pi_j$）。$P_j$ による期待値を $E_j$ と書くと、$\{X=c_j\}$ の上では $X^{\mathsf T}b=c_j^{\mathsf T}b$ なので
$$ E[\rho_\tau(Y-X^{\mathsf T}b)]=\sum_{j=1}^m\pi_jE_j\bigl[\rho_\tau(Y-c_j^{\mathsf T}b)\bigr] $$
である。分位点 の定理「分位点とチェック関数の期待値」を $P_j$ のもとでの $Y$ に使うと、$a\mapsto E_j[\rho_\tau(Y-a)]$ は $Y$ の $P_j$ のもとでの $\tau$ 分位点で最小になるので、各 $j$ で $E_j[\rho_\tau(Y-c_j^{\mathsf T}b)]\ge E_j[\rho_\tau(Y-c_j^{\mathsf T}\beta)]$ である。$\pi_j>0$ を掛けて足せば $E[\rho_\tau(Y-X^{\mathsf T}b)]\ge E[\rho_\tau(Y-X^{\mathsf T}\beta)]$ を得る。$\square$