線形方程式の解法（数値計算）：ランク落ちした行列

数値計算法について困っていることがあり、
皆様のお知恵をお借りしたいと思います。

AX = bのようなシンプルな線形問題についてなのですが、
Aはn<mとなるn*m行列となっており解は無数に存在しています。
求めたい解は無数にある解のうちのどれでもよく任意のものです。

この問題の解き方はいろいろあると思うのですが、
コンピュータ上でこの問題を解かなければならないという事情がありまして、
Aが疎な行列の場合に効率よく解けるという条件をクリアしなければいけません。
そのため特異値分解やガウスの消去法といった疎性を保てない解法は使用できません。

この問題について何かよい解法はご存知ありませんでしょうか？
ご存知の方がいらっしゃいましたらご回答よろしくお願いします。

No.2 ベストアンサー 回答者： kamiyasiro 回答日時： 2015/06/22 23:51

#1です。

間違えました。lassoはL2正則化ではなく、L1正則化です。スミマセン。

この回答へのお礼

kamiyasiroさま、迅速なご回答ありがとうございます。
お礼がおそくなり申し訳ございません。

質問させていただいた問題は解決いたしまして、
逐次近似による残差最小化で解決に至りました。

詳細をご報告させていただきますと、
まずはじめに、共役勾配法によってε= Ax - bを最小化する問題を解いたところ解が得られなかった、ということが質問させていただいた経緯としてありました。
ここで私は、ATA（Aの転置かけるA）が特異な行列の場合共役勾配法が機能しないことがあるのではないかと考え、こちらでの質問に至ったのですが問題は別のところにありました。

私が解いている問題における行列Aの特性を調べてみたところ、
n個の行ベクトルの総和がゼロベクトルになるという性質があることに気がつきました。
この場合右辺のベクトルbの要素の総和もゼロになっている必要があるのですが、
実際はそうなっていませんでした。
そのため、ベクトルbの要素の総和がゼロになるように修正をかけることで、
共役勾配法が上手く機能しました。

結論としては、
0*x = bという問題を無理矢理解こうとしていたことに上手くいかない原因があり、
共役勾配法による残差最小化で解くことができるということがわかりました。


kamiyasiroさまに教えていただいた正則化回帰は今回使いませんでしたが、
統計的手法でそのような方法があることは知らず、今回大変勉強になりました。
統計は専門ではありませんが、統計の分野の有用な方法については勉強していきたいと思いました。
機会がありましたらまた是非教えていただきたいと思います。


今回の質問については、
素早く回答をくださったkamiyasiroさまのご回答をベストアンサーとさせていただきます。
ありがとうございました。

お礼日時：2015/06/23 23:35

No.3 回答者： stomachman 回答日時： 2015/06/23 13:51

スパースなまま扱いたいという事なら、解を逐次近似しちゃどうです？

　　ε= Ax - y
として、テキトーなxから出発し、
　　 |ε|^2 = 0
に近づくようにxを修正していくんです。たとえば（効率の良さはさておいて）「xの第k成分だけを変数として（他の成分は変えずに） |ε|^2を最小化する」という問題を考えれば、これはとても簡単でしょ。この操作をk=1〜mについて一通りやると、この間 |ε|^2は減少し続ける訳です。で、またk=1〜mについて一通りやる。ということを繰り返す。

この回答へのお礼

stomachmanさま、ご回答ありがとうございます。

先ほど質問させていただいた問題は解決いたしまして、
stomachmanさまのおっしゃるような逐次近似による残差最小化で解決に至りました。

詳細をご報告させていただきますと、
まずはじめに、共役勾配法によってε= Ax - bを最小化する問題を解いたところ解が得られなかった、ということが質問させていただいた経緯としてありました。
ここで私は、ATA（Aの転置かけるA）が特異な行列の場合共役勾配法が機能しないことがあるのではないかと考え、こちらでの質問に至ったのですが問題は別のところにありました。

私が解いている問題における行列Aの特性を調べてみたところ、
n個の行ベクトルの総和がゼロベクトルになるという性質があることに気がつきました。
この場合右辺のベクトルbの要素の総和もゼロになっている必要があるのですが、
実際はそうなっていませんでした。
そのため、ベクトルbの要素の総和がゼロになるように修正をかけることで、
共役勾配法が上手く機能しました。

結論としては、
0*x = bという問題を無理矢理解こうとしていたことに上手くいかない原因があり、
stomachmanさまのおっしゃった逐次近似による残差最小化で解くことができるということがわかりました。

勝手に質問した上で勝手に解決してしまい大変恐縮なのですが、
丁寧にご回答いただいたstomachmanさまには感謝いたします。
ありがとうございました。

お礼日時：2015/06/23 23:23

No.1 回答者： kamiyasiro 回答日時： 2015/06/22 23:49

現在、リッジ回帰など正則化回帰の方法として知られている回帰分析のうち、ご質問者のように過飽和でも解ける手法としては、lasso（ラスー）が上げられます。

L2正則化回帰とか、罰則付き回帰と言われています。
　任意の解ではなく、適切に変数選択された解が得られます。
　1996年、スタンフォード大学のティブシャアーニ先生が提案した手法ですが、実装している統計ソフトは限られています。私はフリーの統計ソフトRを使っています。私は、ライブラリlarsを使っていますが、ライブラリglmnetでもできます。