|
mxlib
c++ tools for analyzing astronomical data and other tasks by Jared R. Males. [git repo]
|
Reusable updates that remove rows or columns from matrices represented by thin singular value decompositions.
Let a rank- \(q\) matrix be represented by the thin singular value decomposition
\[A = U \Sigma V^T. \]
To remove physical rows with sorted index set \(R\), form \(F=U[R,:]\). The retained matrix obeys
\[A_{\bar R}^T A_{\bar R} = V \Sigma \left(I-F^T F\right) \Sigma V^T. \]
If \(W\) contains the eigenvectors or right singular vectors of the resulting rank- \(q\) core, the updated right singular directions are \(VW\). Column deletion is the transpose dual: use \(F=V[C,:]\) for deleted columns \(C\), and apply the returned rotation to the unchanged left factor as \(UW\).
Complete singular factors reproduce a direct SVD of the physically retained matrix. Truncated factors instead delete rows or columns exactly from the supplied rank- \(q\) approximation; discarded modes cannot be recovered.
Both current implementations use dense LAPACK operations and have cubic asymptotic cost in \(q\). The API keeps the backend selectable so a future structured secular-equation implementation can preserve the same interface.
Singular values must be finite, nonnegative, and descending. The deleted-side factor must have orthonormal columns; call mx::math::validateSvdDeletionFactor once for a new base factorization, outside repeated deletion loops. Deleted indices must be sorted, unique, and in range, the output rank must be nonzero and no larger than \(q\), and at least one physical row or column must remain.
A successful result contains all \(q\) updated singular values and squared singular values. Only the leading outputRank() columns of rotation() are published. Both mx::math::svdDeletionStatus::success and mx::math::svdDeletionStatus::successWithClamping are usable; test them with mx::math::svdDeletionSucceeded(). The latter records roundoff-scale negative eigenvalues clamped to zero.
Prepare mx::math::svdDeletionResult and mx::math::svdDeletionWorkspace for the largest planned output rank and deletion count before a hot loop. Later compatible operations reuse their allocations. Each concurrent worker must own an independent result and workspace.
Result and workspace objects are move-only handles whose Eigen and LAPACK storage is opaque and destroyed inside mxlib. Spectrum and rotation accessors return unaligned read-only views into result-owned storage; a view remains valid only until its result is prepared, assigned, moved, or destroyed. This ownership boundary permits consumers with different Eigen alignment/SIMD settings from mxlib's build, but it is not a promise of general binary compatibility across arbitrary compilers, C++ standard libraries, or Eigen ABIs.
The factors below are assumed to have been produced by an earlier thin SVD.
For column deletion, pass \(V\) to mx::math::svdRemoveColumns() and apply the returned rotation to \(U\).
Classes | |
| struct | mx::math::svdDeletionConstVectorViewV2< realT > |
| ABI-stable borrowed contiguous-vector storage descriptor. More... | |
| struct | mx::math::svdDeletionConstMatrixViewV2< realT > |
| ABI-stable borrowed column-major matrix storage descriptor. More... | |
| struct | mx::math::svdDeletionConstIndexViewV2 |
| ABI-stable borrowed signed-index storage descriptor. More... | |
| struct | mx::math::svdDeletionAbiV2Tag |
| Type-level ABI tag for the second-generation opaque SVD deletion handles. More... | |
| class | mx::math::svdDeletionResult< realT, abiT > |
| Result of deleting rows or columns from a represented thin SVD. More... | |
| class | mx::math::svdDeletionWorkspace< realT, abiT > |
| Reusable, non-shared storage for SVD deletion operations. More... | |
Typedefs | |
| template<typename realT> | |
| using | mx::math::svdDeletionMatrix = Eigen::Array<realT, Eigen::Dynamic, Eigen::Dynamic, Eigen::ColMajor> |
| Column-major dynamic matrix used by the SVD deletion API. | |
| template<typename realT> | |
| using | mx::math::svdDeletionVector = Eigen::Array<realT, Eigen::Dynamic, 1> |
| Dynamic column vector used by the SVD deletion API. | |
| template<typename realT> | |
| using | mx::math::svdDeletionConstMatrixRef = Eigen::Ref<const svdDeletionMatrix<realT>> |
| Non-owning read-only reference to a compatible column-major SVD deletion matrix. | |
| template<typename realT> | |
| using | mx::math::svdDeletionConstVectorRef = Eigen::Ref<const svdDeletionVector<realT>> |
| Non-owning read-only reference to a compatible SVD deletion vector. | |
Enumerations | |
| enum class | mx::math::svdDeletionBackend { svdDeletionBackend::leadingCovariance , svdDeletionBackend::stableCore , svdDeletionBackend::rankOneSecular } |
| Numerical backend used to delete rows or columns from thin-SVD factors. More... | |
| enum class | mx::math::svdDeletionStatus { svdDeletionStatus::notComputed , svdDeletionStatus::success , svdDeletionStatus::successWithClamping , svdDeletionStatus::invalidInput , svdDeletionStatus::allocationFailure , svdDeletionStatus::workspaceQueryFailure , svdDeletionStatus::solverFailure , svdDeletionStatus::nonFiniteOutput , svdDeletionStatus::invalidSolverOutput , svdDeletionStatus::rescalingOverflow , svdDeletionStatus::nonPositiveSemidefinite , svdDeletionStatus::factorNotOrthonormal , svdDeletionStatus::unsupportedDeletionCount } |
| Completion status for an SVD deletion operation. More... | |
Functions | |
| const char * | mx::math::svdDeletionBackendName (svdDeletionBackend backend) |
| Return a stable text representation of an SVD deletion backend. | |
| const char * | mx::math::svdDeletionStatusName (svdDeletionStatus status) |
| Return a stable text representation of an SVD deletion status. | |
| bool | mx::math::svdDeletionSucceeded (svdDeletionStatus status) noexcept |
| Return true when a status represents usable numerical output. | |
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus | mx::math::validateSvdDeletionFactor (svdDeletionConstMatrixRef< float > factor, float tolerance=0) |
| Validate that a supplied thin singular-vector factor has orthonormal columns. | |
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus | mx::math::validateSvdDeletionFactor (svdDeletionConstMatrixRef< double > factor, double tolerance=0) |
| Validate that a supplied double-precision thin singular-vector factor has orthonormal columns. | |
| template<typename realT> | |
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus | mx::math::svdDeletionLeadingCore (svdDeletionResult< realT > &result, std::type_identity_t< svdDeletionConstVectorRef< realT > > singularValues, std::type_identity_t< svdDeletionConstMatrixRef< realT > > deletedRows, Eigen::Index outputRank, svdDeletionWorkspace< realT > &workspace) |
| Delete supplied singular-factor rows with the full-spectrum symmetric covariance core. | |
| template<typename realT> | |
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus | mx::math::svdDeletionStableCore (svdDeletionResult< realT > &result, std::type_identity_t< svdDeletionConstVectorRef< realT > > singularValues, std::type_identity_t< svdDeletionConstMatrixRef< realT > > deletedRows, Eigen::Index outputRank, svdDeletionWorkspace< realT > &workspace) |
| Delete supplied singular-factor rows with the complement-preserving small-SVD core. | |
| template<typename realT> | |
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus | mx::math::svdDeletionCore (svdDeletionResult< realT > &result, std::type_identity_t< svdDeletionConstVectorRef< realT > > singularValues, std::type_identity_t< svdDeletionConstMatrixRef< realT > > deletedRows, Eigen::Index outputRank, svdDeletionWorkspace< realT > &workspace, svdDeletionBackend backend=svdDeletionBackend::stableCore) |
| Delete supplied singular-factor rows with an explicitly selected backend. | |
| template<typename realT> | |
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus | mx::math::svdRemoveRows (svdDeletionResult< realT > &result, std::type_identity_t< svdDeletionConstVectorRef< realT > > singularValues, std::type_identity_t< svdDeletionConstMatrixRef< realT > > leftFactor, std::span< const Eigen::Index > deletedIndices, Eigen::Index outputRank, svdDeletionWorkspace< realT > &workspace, svdDeletionBackend backend=svdDeletionBackend::stableCore) |
| Delete physical rows from the matrix represented by a thin SVD. | |
| template<typename realT> | |
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus | mx::math::svdRemoveColumns (svdDeletionResult< realT > &result, std::type_identity_t< svdDeletionConstVectorRef< realT > > singularValues, std::type_identity_t< svdDeletionConstMatrixRef< realT > > rightFactor, std::span< const Eigen::Index > deletedIndices, Eigen::Index outputRank, svdDeletionWorkspace< realT > &workspace, svdDeletionBackend backend=svdDeletionBackend::stableCore) |
| Delete physical columns from the matrix represented by a thin SVD. | |
| using mx::math::svdDeletionConstMatrixRef = Eigen::Ref<const svdDeletionMatrix<realT>> |
Non-owning read-only reference to a compatible column-major SVD deletion matrix.
Definition at line 99 of file svdDowndate.hpp.
| using mx::math::svdDeletionConstVectorRef = Eigen::Ref<const svdDeletionVector<realT>> |
Non-owning read-only reference to a compatible SVD deletion vector.
Definition at line 103 of file svdDowndate.hpp.
| using mx::math::svdDeletionMatrix = Eigen::Array<realT, Eigen::Dynamic, Eigen::Dynamic, Eigen::ColMajor> |
Column-major dynamic matrix used by the SVD deletion API.
Definition at line 91 of file svdDowndate.hpp.
| using mx::math::svdDeletionVector = Eigen::Array<realT, Eigen::Dynamic, 1> |
Dynamic column vector used by the SVD deletion API.
Definition at line 95 of file svdDowndate.hpp.
|
strong |
Numerical backend used to delete rows or columns from thin-SVD factors.
Definition at line 55 of file svdDowndate.hpp.
|
strong |
Completion status for an SVD deletion operation.
Definition at line 63 of file svdDowndate.hpp.
| const char * mx::math::svdDeletionBackendName | ( | svdDeletionBackend | backend | ) |
Return a stable text representation of an SVD deletion backend.
| [in] | backend | backend to describe |
Definition at line 1615 of file svdDowndate.cpp.
References leadingCovariance, rankOneSecular, and stableCore.
Referenced by unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), and unitTest::math_svdDowndate_test::TEST_CASE().
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus mx::math::svdDeletionCore | ( | svdDeletionResult< realT > & | result, |
| std::type_identity_t< svdDeletionConstVectorRef< realT > > | singularValues, | ||
| std::type_identity_t< svdDeletionConstMatrixRef< realT > > | deletedRows, | ||
| Eigen::Index | outputRank, | ||
| svdDeletionWorkspace< realT > & | workspace, | ||
| svdDeletionBackend | backend = svdDeletionBackend::stableCore ) |
Delete supplied singular-factor rows with an explicitly selected backend.
rankOneSecular accepts either no deleted rows, which returns the identity update, or exactly one deleted row. It solves the same covariance core as leadingCovariance by transforming the diagonal-minus-rank-one problem to a positive rank-one secular equation. LAPACK-style deflation handles negligible update components and clustered poles at a roundoff-scaled tolerance; post-solve validation uses dimension-scaled bounds. See [3] and [12].
| [out] | result | updated spectrum, rotation, and diagnostics |
| [in] | singularValues | descending base singular values |
| [in] | deletedRows | deleted-side factor rows |
| [in] | outputRank | number of leading updated directions to publish |
| [in,out] | workspace | reusable, worker-private scratch storage |
| [in] | backend | numerical backend |
Definition at line 620 of file svdDowndate.hpp.
References mx::math::svdDeletionResult< realT, abiT >::backend(), mx::math::svdDeletionResult< realT, abiT >::outputRank(), mx::math::svdDeletionResult< realT, abiT >::singularValues(), and stableCore.
Referenced by unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), and unitTest::math_svdDowndate_test::TEST_CASE().
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus mx::math::svdDeletionLeadingCore | ( | svdDeletionResult< realT > & | result, |
| std::type_identity_t< svdDeletionConstVectorRef< realT > > | singularValues, | ||
| std::type_identity_t< svdDeletionConstMatrixRef< realT > > | deletedRows, | ||
| Eigen::Index | outputRank, | ||
| svdDeletionWorkspace< realT > & | workspace ) |
Delete supplied singular-factor rows with the full-spectrum symmetric covariance core.
Given deleted-side rows F, this solves
\[H = \Sigma (I-F^T F) \Sigma = W \Lambda W^T. \]
The result rotation is W and its singular values are sqrt(diag(Lambda)). The complete spectrum is evaluated for PSD validation even when only outputRank leading directions are published. This backend forms normal equations and therefore does not promise high relative accuracy for the smallest singular values. The rankOneSecular backend evaluates this same core in quadratic time when exactly one row is deleted.
| [out] | result | updated spectrum, rotation, and diagnostics |
| [in] | singularValues | descending base singular values |
| [in] | deletedRows | deleted-side factor rows |
| [in] | outputRank | number of leading updated directions to publish |
| [in,out] | workspace | reusable, worker-private scratch storage |
Definition at line 560 of file svdDowndate.hpp.
References mx::math::svdDeletionResult< realT, abiT >::outputRank(), and mx::math::svdDeletionResult< realT, abiT >::singularValues().
Referenced by unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), and unitTest::math_svdDowndate_test::TEST_CASE().
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus mx::math::svdDeletionStableCore | ( | svdDeletionResult< realT > & | result, |
| std::type_identity_t< svdDeletionConstVectorRef< realT > > | singularValues, | ||
| std::type_identity_t< svdDeletionConstMatrixRef< realT > > | deletedRows, | ||
| Eigen::Index | outputRank, | ||
| svdDeletionWorkspace< realT > & | workspace ) |
Delete supplied singular-factor rows with the complement-preserving small-SVD core.
Let F contain deleted-side singular-factor rows and choose B so that B^T B = I - F F^T. The at-most (q+c) x q core
\[K = \begin{bmatrix}(I-F^TF)\Sigma \\ BF\Sigma\end{bmatrix} \]
obeys K^T K = Sigma (I-F^T F) Sigma. Its right singular vectors are the preserved-side rotation. This is the default generic backend because it avoids explicitly squaring the represented singular values. See [2] and [18].
This backend and leadingCovariance use dense LAPACK solvers and therefore have cubic asymptotic cost in the base rank. The rankOneSecular backend instead uses a structured quadratic-time solve for one-row deletion.
| [out] | result | updated spectrum, rotation, and diagnostics |
| [in] | singularValues | descending base singular values |
| [in] | deletedRows | deleted-side factor rows |
| [in] | outputRank | number of leading updated directions to publish |
| [in,out] | workspace | reusable, worker-private scratch storage |
Definition at line 594 of file svdDowndate.hpp.
References mx::math::svdDeletionResult< realT, abiT >::outputRank(), and mx::math::svdDeletionResult< realT, abiT >::singularValues().
Referenced by unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), and unitTest::math_svdDowndate_test::TEST_CASE().
| const char * mx::math::svdDeletionStatusName | ( | svdDeletionStatus | status | ) |
Return a stable text representation of an SVD deletion status.
| [in] | status | status to describe |
Definition at line 1629 of file svdDowndate.cpp.
References allocationFailure, factorNotOrthonormal, invalidInput, invalidSolverOutput, nonFiniteOutput, nonPositiveSemidefinite, notComputed, rescalingOverflow, solverFailure, success, successWithClamping, unsupportedDeletionCount, and workspaceQueryFailure.
Referenced by unitTest::math_svdDowndate_test::TEST_CASE(), and unitTest::math_svdDowndate_test::TEST_CASE().
|
noexcept |
Return true when a status represents usable numerical output.
| [in] | status | status to classify |
Definition at line 1663 of file svdDowndate.cpp.
References success, and successWithClamping.
Referenced by unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), and unitTest::math_svdDowndate_test::TEST_CASE().
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus mx::math::svdRemoveColumns | ( | svdDeletionResult< realT > & | result, |
| std::type_identity_t< svdDeletionConstVectorRef< realT > > | singularValues, | ||
| std::type_identity_t< svdDeletionConstMatrixRef< realT > > | rightFactor, | ||
| std::span< const Eigen::Index > | deletedIndices, | ||
| Eigen::Index | outputRank, | ||
| svdDeletionWorkspace< realT > & | workspace, | ||
| svdDeletionBackend | backend = svdDeletionBackend::stableCore ) |
Delete physical columns from the matrix represented by a thin SVD.
For A=U Sigma V^T, this gathers V[deletedIndices,:]. The returned rotation applies to U. Supplying complete factors makes the deletion identical to a direct SVD of the physically retained matrix. Supplying truncated factors deletes columns exactly from that represented low-rank matrix.
| [out] | result | updated spectrum, rotation, and diagnostics |
| [in] | singularValues | descending base singular values |
| [in] | rightFactor | thin right factor V |
| [in] | deletedIndices | sorted, unique column indices to delete |
| [in] | outputRank | number of leading updated directions |
| [in,out] | workspace | reusable, worker-private scratch |
| [in] | backend | numerical backend |
Definition at line 676 of file svdDowndate.hpp.
References mx::math::svdDeletionResult< realT, abiT >::backend(), mx::math::svdDeletionResult< realT, abiT >::outputRank(), mx::math::svdDeletionResult< realT, abiT >::singularValues(), and stableCore.
Referenced by unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), and unitTest::math_svdDowndate_test::TEST_CASE().
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus mx::math::svdRemoveRows | ( | svdDeletionResult< realT > & | result, |
| std::type_identity_t< svdDeletionConstVectorRef< realT > > | singularValues, | ||
| std::type_identity_t< svdDeletionConstMatrixRef< realT > > | leftFactor, | ||
| std::span< const Eigen::Index > | deletedIndices, | ||
| Eigen::Index | outputRank, | ||
| svdDeletionWorkspace< realT > & | workspace, | ||
| svdDeletionBackend | backend = svdDeletionBackend::stableCore ) |
Delete physical rows from the matrix represented by a thin SVD.
For A=U Sigma V^T, this gathers U[deletedIndices,:]. The returned rotation applies to V. Supplying complete factors makes the deletion identical to a direct SVD of the physically retained matrix. Supplying truncated factors deletes rows exactly from that represented low-rank matrix.
| [out] | result | updated spectrum, rotation, and diagnostics |
| [in] | singularValues | descending base singular values |
| [in] | leftFactor | thin left factor U |
| [in] | deletedIndices | sorted, unique row indices to delete |
| [in] | outputRank | number of leading updated directions |
| [in,out] | workspace | reusable, worker-private scratch |
| [in] | backend | numerical backend |
Definition at line 646 of file svdDowndate.hpp.
References mx::math::svdDeletionResult< realT, abiT >::backend(), mx::math::svdDeletionResult< realT, abiT >::outputRank(), mx::math::svdDeletionResult< realT, abiT >::singularValues(), and stableCore.
Referenced by unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), and unitTest::math_svdDowndate_test::TEST_CASE().
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus mx::math::validateSvdDeletionFactor | ( | svdDeletionConstMatrixRef< double > | factor, |
| double | tolerance = 0 ) |
Validate that a supplied double-precision thin singular-vector factor has orthonormal columns.
| [in] | factor | thin singular-vector factor to validate |
| [in] | tolerance | maximum absolute Gram-matrix error, or zero for automatic |
Definition at line 536 of file svdDowndate.hpp.
| MXLIB_SVD_DELETION_HEADER_ADAPTER svdDeletionStatus mx::math::validateSvdDeletionFactor | ( | svdDeletionConstMatrixRef< float > | factor, |
| float | tolerance = 0 ) |
Validate that a supplied thin singular-vector factor has orthonormal columns.
This is an optional one-time base-factor check. Hot deletion calls assume the factor contract and do not repeat this O(n q^2) operation. A zero tolerance selects a dimension-scaled default.
| [in] | factor | thin singular-vector factor to validate |
| [in] | tolerance | maximum absolute Gram-matrix error, or zero for automatic |
Definition at line 525 of file svdDowndate.hpp.
References validateSvdDeletionFactor().
Referenced by unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), unitTest::math_svdDowndate_test::TEST_CASE(), and validateSvdDeletionFactor().