Skip to content

Matrix::pseudoinverse()` reads out of bounds for every tall matrix #4

Description

@Jeckerson

Summary

tensor_pseudoinverse() passes the wrong inner dimension to cblas_dgemm. For any matrix with
more rows than columns it reads past the end of the n × n right singular vectors. The result is
silently wrong for small matrices, entirely non-finite for larger ones, and dependent on unrelated
heap state in between — so the same input can produce different output in different programs.

Affects master (b197cbe). Found while building a parity harness: the operation produced
different results on two consecutive runs of the same script.

Reproduction

<?php
// A 500x2 matrix. Nothing about the values matters.
mt_srand(11);
$samples = [];
for ($i = 0; $i < 500; ++$i) {
    $samples[] = [mt_rand(-1000, 1000) / 100, mt_rand(-1000, 1000) / 100];
}

$a = Tensor\Matrix::quick($samples);
$p = $a->pseudoinverse();

$nonFinite = 0;
foreach ($p->asArray() as $row) {
    foreach ($row as $value) {
        if (!is_finite($value)) {
            ++$nonFinite;
        }
    }
}

echo "non-finite elements: {$nonFinite} of 1000\n";   // 1000 of 1000

The first Moore-Penrose condition fails with it:

A max abs(A·A⁺·A − A)
2×3 5.3e-15
100×4 1.2e-14
500×2 all elements non-finite
2×500 7.1e-15

Scanning m for each n, the first shape that produces non-finite output is m = 203 at n = 2 and
m = 151 at n = 3. Below those thresholds the read still goes out of bounds; it just lands on
memory that happens to be mapped, so the answer looks plausible.

Cause

ext/include/linear_algebra.c, in tensor_pseudoinverse():

cblas_dgemm(CblasRowMajor, CblasTrans, CblasTrans, n, m, m, 1.0, vvt, n, vu, m, 0.0, vb, m);
/*                                          K ---^                                          */

K is the inner dimension of the product. With CblasTrans on the first operand, CBLAS reads it
as K × M — here m rows of n — but vvt is only n × n, as allocated twenty lines above and
as LAPACKE_dgesdd filled it. Every call with m > n therefore reads (m − n) × n doubles past
the end of the buffer.

The correct inner dimension is the rank of the thin SVD, k = MIN(m, n), which the function
already computes. It happens to equal m for square and wide matrices, which is why the existing
2×3 test passes.

Fix

-    cblas_dgemm(CblasRowMajor, CblasTrans, CblasTrans, n, m, m, 1.0, vvt, n, vu, m, 0.0, vb, m);
+    cblas_dgemm(CblasRowMajor, CblasTrans, CblasTrans, n, m, k, 1.0, vvt, n, vu, m, 0.0, vb, m);

The leading dimensions are already right: lda = n selects the first k rows of vvt, and
ldb = m selects the first k columns of vu.

With the fix, every shape tried satisfies A·A⁺·A = A to ~1e-14, including 500×2, 203×2, 151×3,
600×2 and 1000×3. The existing suite stays green.

Note on test coverage

MatrixTest::pseudoinverse() carries @requires extension tensor, but the extension is named
tensor_ext. That test, and three others (eig, eigSymmetric, svd), have therefore been
skipped rather than run since the rename. Fixing the annotation is a separate one-line change and
is what makes this bug testable.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions