Tag: algorithm

Finding the Nearest Valid Correlation Matrix with Higham’s Algorithm

Introduction

In quantitative finance, correlation matrices are essential for portfolio optimization, risk management, and asset allocation. However, real-world data often results in correlation matrices that are invalid due to various issues:

  • Merging Non-Overlapping Datasets: If correlations are estimated separately for different periods or asset subsets and then stitched together, the resulting matrix may lose its positive semidefiniteness.
  • Manual Adjustments: Risk/assert managers sometimes override statistical estimates based on qualitative insights, inadvertently making the matrix inconsistent.
  • Numerical Precision Issues: Finite sample sizes or noise in financial data can lead to small negative eigenvalues, making the matrix slightly non-positive semidefinite.
Continue reading

Efficient Rolling Median with the Two-Heaps Algorithm. O(log n)

Calculating the median of data points within a moving window is a common task in fields like finance, real-time analytics and signal processing. The main applications are anomal- and outlier-detection / removal.

Fig 1. A slow-moving signal with outlier-spikes (blue) and the rolling median filter (orange).

A naive implementation based on sorting is costly—especially for large window sizes. An elegant solution is the Two-Heaps Rolling Median algorithm, which maintains two balanced collections to quickly calculate the median as new data arrives and old data departs.

Continue reading