GCArullo / GCArullo/JenpyROQ

Gram-Schmidt well-conditioning

Open
#2 0 comments 0 reactions 0 assignees View on GitHub
enhancement question
Dominant language
Python
Stars
7
Forks
2
PR merge metrics
No merged PRs in 30d

Description

The interpolant construction algorithm in principle does not need the Gram-Schmidt (GS) algorithm to be applied to the basis, i.e the waveforms can be directly used as basis vectors. For the moment, this seems to work in all cases tested without any numerical inaccuracies (the `debug` option monitors the conditioning of the basis matrix). If signs of ill-conditioning appear in future applications (e.g. large numbers of repeated interpolant points), what discussed below might help solving the issue.

---

One might imagine that a GS-tted basis would be "optimal" (i.e. it would require less elements) because redundancies would be avoided. This last intuition should be given a more rigorous backup.

However, when applying the GS algorithm on long seglens (~128), the basis matrix becomes ill-conditioned (most probably due to the sparsity of elements and the "disparity" of the basis vectors, compared to a basis made of waveforms) and its inversion acquires large errors. Hence, for the moment, GS is not applied to the basis.

Assuming GS would indeed improve the algorithm^*, one can apply a regularised GS algorithm to fix the ill-conditioning issue.
Several options are already known:

1. See "Numerical stability" and "Alternatives" [here](https://en.wikipedia.org/wiki/Gram–Schmidt_process).

a. Modified Gram-Schmidt
b. Householder transformations
c. Cholesky decomposition

2. Regularisation discussed in `Field+ (Phys. Rev. X 4, 031006), pg.14, Appendix A and Refs.[66,67,68]`.
Relevant codes to be compared against are GreedyCPP and LALInference.

3. [Antil+](https://arxiv.org/abs/1210.0577) Appendix A.2 suggests to use the residuals to construct the basis matrix.

5. See the discussion [here](https://scicomp.stackexchange.com/questions/31432/a-fast-way-to-check-if-a-matrix-is-ill-conditioned-and-turning-it-into-well-con).

-----------

^* One might question the practical advantages of improving the algorithm in cases where no signs of ill-conditioning appear without GS. In fact, since the convergence is exponential, small improvements in the reduction of basis element numbers won't have a large impact in practise.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by locating the interpolant construction algorithm and its `debug` conditioning check. Review how the basis matrix is built and compare the proposed Gram-Schmidt alternatives and regularisation references. Done means establishing whether Gram-Schmidt improves the algorithm and addressing the reported ill-conditioning without introducing numerical errors.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.