Gram-Schmidt well-conditioning
- 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