2026-05-10

行列方程式の情報不足やランク不足に対する処置

研究で方程式の数が足りない行列方程式やランク不足に悩まされることが増えてきたため、その取り扱い方をまとめます

数学線形代数

考えること

$m \times n \ (m < n)$ の行列 $A$ に対して、方程式

\boldsymbol{y} = A\boldsymbol{x}

を考えてみる。つまり、 $\boldsymbol{y} \in \mathbb{R}^m, \boldsymbol{x} \in \mathbb{R}^n$

この方程式において、既知の $\boldsymbol{y}$ と $A$ から未知の $\boldsymbol{x}$ を復元することを目標とする。

もし $\boldsymbol{x} \in \mathbb{R}^n$ を一意に復元したいなら、本来は $n$ 個分の独立な情報が必要になる。しかし、今観測できている方程式の数は $m$ 本しかなく、 $m < n$ である。したがって、単純な逆行列による解法は使えない。困った。

まずは、行列 $A$ の行がすべて独立である場合、つまり

\operatorname{rank} A = m

である場合を考える。このとき、次元定理より

\dim \ker A = n - \operatorname{rank} A = n - m

となる。

つまり、 $\boldsymbol{y}$ と $A$ が与えられても、 $\boldsymbol{x}$ は一意には定まらず、 $n - m$ 次元分の自由度が残ってしまう。言い換えると、観測された $m$ 本の方程式だけでは、 $\boldsymbol{x}$ のうち $n - m$ 次元分の情報が見えていない。

厳密には...

上では「解の次元」という言い方をしているが、実際の解集合は以下の式で表されるアフィン空間となる。 $\boldsymbol{x}_0$ はこの方程式の特解で、何か一つでも方程式を満たすベクトルが見つかればそれを採用してよい。（線形な方程式の解の構造はだいたいこうでしょ）

\boldsymbol{x} = \boldsymbol{x}_0 + \ker A

ここで重要なのは、 $\ker A$ 方向の成分は $A$ をかけると消えてしまうという点である。実際、任意の $\boldsymbol{v} \in \ker A$ について、

A(\boldsymbol{x}_0 + \boldsymbol{v}) = A\boldsymbol{x}_0 + A\boldsymbol{v} = \boldsymbol{y}

となる。

したがって、 $\boldsymbol{x}_0$ に $\ker A$ の成分をどれだけ足しても、観測される $\boldsymbol{y}$ は変わらない。この意味で、 $\ker A$ は「観測からは区別できない方向」を表している。

本記事では、このように $m < n$ で方程式の本数が足りない状況において、残ってしまった $n - m$ 次元分の自由度をどのように扱うかを考える。

さらに実際の応用、例えばRLNCやMIMOなどのような通信ネットワーク・信号処理の文脈では、データの欠損や線形従属な情報の受信などにより、行列 $A$ が最大ランクを満たさないケースもしばしば発生する。その場合には、そもそも独立な情報が $m$ 本分すら得られていないことになり、不足する自由度はさらに大きくなる。

仮定

本記事では、以下の条件を仮定として進めていく。

観測された $\boldsymbol{y}$ は、ある真のベクトル $\boldsymbol{x}_*$ から生成されたものとする。つまり、
$\boldsymbol{y} = A\boldsymbol{x}_*$
を満たす $\boldsymbol{x}_*$ が存在すると仮定する。言い換えると、
$\boldsymbol{y} \in \operatorname{Im} A$
である。
まずはノイズの影響は考えず、方程式 $\boldsymbol{y} = A\boldsymbol{x}$ を厳密に満たす解が存在する場合を考える。
追加の独立な方程式が十分に集まり、拡張された係数行列 $\tilde{A}$ が
$\operatorname{rank} \tilde{A} = n$
を満たせば、 $\boldsymbol{x}$ は一意に復元できるものとする。

何が足りていないのか

いま、未知ベクトル $\boldsymbol{x}$ は $n$ 次元の情報を持っている。一方で、観測として得られている $\boldsymbol{y}$ は $m$ 次元であり、 $m < n$ である。

したがって、観測 $\boldsymbol{y}$ だけから $\boldsymbol{x}$ のすべてを決めることはできない。最大ランク $\operatorname{rank} A = m$ の場合であっても、

\dim \ker A = n - m

であるから、 $n - m$ 次元分の自由度が残る。

この $n - m$ 次元分が、今回「どうにかして埋めたい」部分である。

ただし、ここでいう「埋める」には二つの意味がある。一つは、本当に追加の情報を集めて、足りない方程式を補うという意味である。もう一つは、情報そのものは足りないままだが、何らかの仮定や基準を追加して、無数にある解の中から一つを選ぶという意味である。

前者は、例えば通信で追加のパケットを受信することに対応する。後者は、例えば「ノルムが最小の解を選ぶ」「疎な解を選ぶ」「非負な解だけを考える」といった制約を入れることに対応する。

方針1：追加の情報を集める

最も直接的な方法は、不足している情報を追加で集めることである。これは、行列 $A$ に新しい行を追加していくことに対応する。

例えば、新しく一つの方程式

y_{m+1} = \boldsymbol{a}_{m+1}^T\boldsymbol{x}

が得られたとする。このとき、もとの方程式は

\begin{pmatrix} \boldsymbol{y} \\ y_{m+1} \end{pmatrix} = \begin{pmatrix} A \\ \boldsymbol{a}_{m+1}^T \end{pmatrix} \boldsymbol{x}

のように拡張される。

ここで重要なのは、新しく得られた方程式が既存の方程式と独立であるかどうかである。もし $\boldsymbol{a}_{m+1}^T$ が、すでにある $A$ の行ベクトルたちの線形結合で表されるなら、方程式の本数は増えてもランクは増えない。

つまり、見かけ上は情報が増えたように見えても、実際には新しい情報は増えていない。

逆に、新しく得られた方程式が既存の方程式と独立であれば、係数行列のランクは増える。このようにして独立な方程式を追加していき、最終的に拡張された係数行列 $\tilde{A}$ が

\operatorname{rank} \tilde{A} = n

を満たせば、 $\ker \tilde{A} = \{\boldsymbol{0}\}$ となり、 $\boldsymbol{x}$ は一意に定まる。でも、私の研究ではリアルタイム性を追求しているため、こんなことはできない。

RLNCの文脈では、これは「十分な数の線形独立な符号化パケットを集めるまで復号を待つ」ことに対応する。受信したパケットの本数が多くても、それらが線形従属であれば復号には不十分である。一方で、独立なパケットが $n$ 本集まれば、元の $n$ 個のパケットを復元できる。

方針2：今ある情報だけで解を一つ選ぶ

しかし、常に追加の情報が得られるとは限らない。通信路の制約、欠損、観測コストなどの理由により、 $m$ 本の方程式しか使えない場合もある。

この場合、 $\boldsymbol{y} = A\boldsymbol{x}$ を満たす解は無数に存在する。したがって、観測だけから真の $\boldsymbol{x}$ を完全に特定することはできない。

そこで、次に考えるのは「どの解を代表として選ぶか」である。

例えば、解集合

\boldsymbol{x} = \boldsymbol{x}_0 + \ker A

の中から、ノルムが最も小さいものを選ぶという方針がある。これは、余計な成分をできるだけ含まない解を選ぶという考え方である。

このような解は、擬似逆行列 $A^+$ を用いて

\boldsymbol{x} = A^+\boldsymbol{y}

と表される。

この解は、 $\boldsymbol{y} = A\boldsymbol{x}$ を満たす解の中で、

\lVert \boldsymbol{x} \rVert_2

が最小となる解である。

つまり、足りない $n - m$ 次元分の自由度を「ノルムが最小になるように」埋めていると見ることができる。やっぱり困った時は最小二乗法。

方針3：事前情報を使う（私の研究の本筋！）

事前情報とは何か

別の考え方として、 $\boldsymbol{x}$ について何らかの事前情報がある場合には、その情報を使って解を選ぶことができる。

事前情報とは、方程式 $\boldsymbol{y} = A\boldsymbol{x}$ そのものからは得られないが、対象についてすでに知っている性質や、別の仕組みから得られる予測のことである。

例えば、「この値は急には変わらない」「多くの成分は $0$ である」「成分は非負である」「前時刻の状態からだいたい予測できる」といった情報は、観測だけでは足りない自由度を埋めるための手がかりになる。

つまり、方程式だけでは足りない部分を、問題固有の知識によって補うという方針である。

例1：推測航法を事前情報として使う

ここで、事前情報を使う例として推測航法を考えてみる。

推測航法では、現在の位置や状態を観測だけから決めるのではなく、一つ前の時刻の状態と、その間に加わった入力や移動量から現在の状態を予測する。例えば、時刻 $t$ における未知の状態を $\boldsymbol{x}_t$ とすると、前時刻の推定値 $\hat{\boldsymbol{x}}_{t-1}$ と入力 $\boldsymbol{u}_t$ を用いて、

\boldsymbol{x}_t \approx F\hat{\boldsymbol{x}}_{t-1} + B\boldsymbol{u}_t

のように予測できる場合がある。

ここで

\boldsymbol{x}_{\mathrm{prior}} = F\hat{\boldsymbol{x}}_{t-1} + B\boldsymbol{u}_t

とおくと、 $\boldsymbol{x}_{\mathrm{prior}}$ は「観測する前に、たぶんこのあたりにいるだろう」と予測された値である。

一方で、観測から得られる方程式は

\boldsymbol{y} = A\boldsymbol{x}_t

である。しかし、 $m < n$ であるため、この観測だけでは $\boldsymbol{x}_t$ を一意に決めることはできない。

そこで、観測を満たす解の中から、推測航法による予測値に最も近いものを選ぶことを考える。つまり、

\min_{\boldsymbol{x}_t} \lVert \boldsymbol{x}_t - \boldsymbol{x}_{\mathrm{prior}} \rVert_2^2 \quad \text{subject to} \quad A\boldsymbol{x}_t = \boldsymbol{y}

という問題を考える。

これは、解集合

\boldsymbol{x}_t = \boldsymbol{x}_0 + \ker A

の中から、推測航法で得られた予測値 $\boldsymbol{x}_{\mathrm{prior}}$ に最も近い点を選ぶ、という意味である。

つまり、観測だけでは決まらない $\ker A$ 方向の自由度を、「前時刻からの運動モデルではこのあたりにいるはず」という事前情報で埋めていると見ることができる。

もし観測にノイズが含まれる場合には、等式制約として扱うのではなく、

\min_{\boldsymbol{x}_t} \left( \lVert A\boldsymbol{x}_t - \boldsymbol{y} \rVert_2^2 + \lambda \lVert \boldsymbol{x}_t - \boldsymbol{x}_{\mathrm{prior}} \rVert_2^2 \right)

のように書くこともできる。

第一項は、観測 $\boldsymbol{y}$ にどれだけ合っているかを表す。第二項は、推測航法による予測 $\boldsymbol{x}_{\mathrm{prior}}$ からどれだけ離れているかを表す。 $\lambda > 0$ は、この事前情報をどれくらい信用するかを決めるパラメータである。

$\lambda$ を大きくすると、推測航法による予測をより強く信じることになる。逆に $\lambda$ を小さくすると、観測の方をより重視することになる。

ただし、推測航法による予測はあくまで予測であり、真の値そのものではない。移動量の誤差やセンサのズレが積み重なると、予測値は少しずつ真の状態からずれていく。そのため、推測航法を使う場合には、「予測を絶対に正しいものとして固定する」のではなく、「観測だけでは足りない部分を補うための柔らかい制約」として使うのが自然である。

この例では、足りない $n - m$ 次元分の自由度を「過去の状態と運動モデルから見て自然な方向に」埋めていると解釈できる。

例2：疎性を事前情報として使う

例えば、 $\boldsymbol{x}$ の多くの成分が $0$ であると分かっているなら、疎な解を選ぶのが自然である。この場合、単にノルム最小の解を選ぶのではなく、非ゼロ成分が少ない解を優先する。

理想的には、

\min_{\boldsymbol{x}} \lVert \boldsymbol{x} \rVert_0 \quad \text{subject to} \quad A\boldsymbol{x} = \boldsymbol{y}

のような問題を考えることになる。ここで $\lVert \boldsymbol{x} \rVert_0$ は、 $\boldsymbol{x}$ の非ゼロ成分の数を表す。

ただし、この問題はそのままでは扱いにくいため、実際には $L^1$ ノルムを用いて

\min_{\boldsymbol{x}} \lVert \boldsymbol{x} \rVert_1 \quad \text{subject to} \quad A\boldsymbol{x} = \boldsymbol{y}

のような形に緩和して考えることが多い。

この場合、足りない $n - m$ 次元分の自由度を「なるべく疎になるように」埋めていると解釈できる。

同じように、 $\boldsymbol{x}$ の成分が非負であることが分かっているなら、

\boldsymbol{x} \ge \boldsymbol{0}

という制約を加えることができる。また、成分の大きさに上限がある、滑らかである、整数である、などの情報があれば、それらも解を選ぶための追加条件として使うことができる。

方針4：正則化で安定な解を選ぶ

実際のデータでは、観測にノイズが含まれることも多い。その場合、

\boldsymbol{y} = A\boldsymbol{x}

を厳密に満たす $\boldsymbol{x}$ が存在しないこともある。

このときは、方程式を完全に満たす解ではなく、

A\boldsymbol{x} \approx \boldsymbol{y}

となるような解を考える。

代表的には、残差

\lVert A\boldsymbol{x} - \boldsymbol{y} \rVert_2^2

を小さくする最小二乗法を考える。しかし、 $m < n$ のままでは最小二乗解も一般には一意に定まらない。

そこで、解の大きさを抑える項を加えて、

\min_{\boldsymbol{x}} \left( \lVert A\boldsymbol{x} - \boldsymbol{y} \rVert_2^2 + \lambda \lVert \boldsymbol{x} \rVert_2^2 \right)

のような問題を考える。ここで $\lambda > 0$ は正則化の強さを表すパラメータである。

これは、観測にできるだけ合うようにしつつ、解が大きくなりすぎないようにする方法である。言い換えると、足りない自由度を「解が安定になるように」埋めていると見ることができる。

$\lambda$ を大きくすると、解の大きさを抑える効果が強くなる。一方で、 $\lambda$ を小さくすると、観測 $\boldsymbol{y}$ により強く合わせることになる。

したがって、正則化は「観測への適合」と「解の安定性」のバランスを取る方法である。

ランク不足の場合

ここまでは、基本的に $A$ が最大ランク

\operatorname{rank} A = m

を持つ場合を考えてきた。

しかし実際には、受け取った方程式が互いに線形従属であるなどの理由により、 $A$ が最大ランクを持たない場合がある。このとき、

r = \operatorname{rank} A < m

とおくと、

\dim \ker A = n - r

となる。

つまり、方程式の本数は $m$ 本あったとしても、独立な情報は $r$ 本分しかない。そのため、不足している自由度は、本来期待していた $n - m$ ではなく、

n - r

まで増えてしまう。

この意味で、ランク不足とは「ただでさえ $m < n$ で情報が足りない状況において、さらに有効な情報量が減ってしまう現象」と解釈できる。

通信の文脈で言えば、RLNCでは受信した符号化パケットの本数が十分に見えても、それらの係数ベクトルが線形従属であれば、元のパケットを復元するには不十分である。また、MIMOでは通信路行列のランクが低いと、複数の送信ストリームを受信側で十分に分離できない。

したがって、ランク不足が起きている場合には、単に方程式の本数を見るのではなく、実際にどれだけの独立な情報が得られているか、つまり $\operatorname{rank} A$ を見る必要がある。

まとめ

$m \times n \ (m < n)$ の行列 $A$ に対して

\boldsymbol{y} = A\boldsymbol{x}

を考えると、未知ベクトル $\boldsymbol{x}$ は $n$ 次元であるのに対して、観測として得られる方程式は $m$ 本しかない。

そのため、 $A$ が最大ランク $\operatorname{rank} A = m$ を持つ場合であっても、

\dim \ker A = n - m

となり、 $n - m$ 次元分の自由度が残る。

この不足した自由度を扱う方法は、大きく分けて二つある。

一つは、追加の情報を集める方法である。これは、新しい独立な方程式を追加し、係数行列のランクを $n$ まで上げることに対応する。

もう一つは、現在得られている情報だけを使い、追加の基準や仮定によって解を一つ選ぶ方法である。最小ノルム解、疎な解、非負制約付きの解、正則化された解などは、すべてこの考え方に含まれる。

さらに、 $A$ がランク不足である場合には、独立な情報の数は $m$ ではなく $\operatorname{rank} A = r$ となる。このとき、不足する自由度は $n - r$ となり、問題はさらに不定になる。

したがって、劣決定な線形方程式を扱うときに重要なのは、単に方程式の本数を見ることではなく、どれだけの独立な情報が得られているか、そして足りない自由度をどのような基準で補うかである。

後記

図が何もなくて抽象的な話ばかりだとAIの出力をただ眺めているのと変わらないですね。この記事のレベルならまだAIと対話していた方が有意義かもしれないです。以後、もっとわかりやすく書けるようにがんばりますね。