Help us understand the problem. What is going on with this article?

コレスキー分解をJavaScriptで実装する

More than 1 year has passed since last update.

1. 背景

※ この記事では実行列のみを対象としている。

行列 $A$ が対称かつ正定値のとき、下三角行列 $L$ とその転置によって $A$ を以下のように分解できることが知られており、そのような分解をコレスキー分解(Cholesky Decomposition, Cholesky Factorization)と呼ぶ。

$$
A = L L^T
$$

Pythonならnumpy.linalg.choleskyによってコレスキー分解をすることが可能だが、JavaScriptのメジャーなライブラリには実装されていない。個人的にJavaScriptで行列計算を行いたい場合はmath.jsTensorFlow.jsをまず検討するのだが、前者にはLU分解やQR分解、後者にはQR分解が実装されているだけである。
コレスキー分解を提供しているJavaScriptのライブラリも無くはないのだが、今回は自分で実装することにした。

2. 実装

以下のページを参考に実装した。コード上のindex等はこの記事に合わせている。
https://rosettacode.org/wiki/Cholesky_decomposition

function choleskyDecomposition(matrix) {
  // Argument "matrix" can be either math.matrix or standard 2D array
  const A = math.matrix(matrix);
  // Matrix A must be symmetric
  console.assert(math.deepEqual(A, math.transpose(A)));

  const n = A.size()[0];
  // Prepare 2D array with 0
  const L = new Array(n).fill(0).map(_ => new Array(n).fill(0));

  d3.range(n).forEach(i => {
    d3.range(i+1).forEach(k => {
      const s = d3.sum(d3.range(k).map(j => L[i][j]*L[k][j]));
      L[i][k] = i === k ? math.sqrt(A.get([k, k]) - s) : 1/L[k][k] * (A.get([i, k]) - s);
    })
  });
  return L;
}

d3.jsとmath.jsに依存している。d3の依存性を除きたければfor文等で容易に代替できるはず。

3. Usage

二次元配列またはmath.jsのmatrixを引数に与えると、二次元配列として行列 $L$ を返す。
以下のようにするとコレスキー分解の正しさを確かめることができる。

const m1 = [[25, 15, -5],
            [15, 18,  0],
            [-5,  0, 11]];
const L1 = choleskyDecomposition(m1);

math.deepEqual(m1, math.multiply(L1, math.transpose(L1)))
// => true

4. Demo

JavaScriptでインタラクティブなノートブックを作成できるObservableというサービスがあり、そこに公開している。
https://observablehq.com/@sw1227/cholesky-decomposition

sw1227
データ分析・可視化 / 地理空間情報 / 機械学習 / シミュレーション / Generative Art などに興味があります。以下のリンクで可視化を公開しています。 https://observablehq.com/@sw1227
https://sw1227.hatenablog.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした