Posdef matrix: private API

posdef_accepts and posdef_repair! are the two steps of posdef! that each algorithm of Posdef owns: the test that leaves a matrix unchanged, and the repair. clipped_correlation, clipped_repair_holds and higham_alternating_projections are the steps of ClippedNearestCorrelation. assert_posdef_repair is the last step of every repair: it refuses a result that is not positive semidefinite to round-off.

zero_variance_rows! is the helper of posdef! and matrix_processing_block! for a constant variable. It sets the row and column of each zero variance to zero, and returns the block of positive variances that the repair works on. zero_variance_block! runs a verb on that block and writes it back, so posdef!, denoise! and detone! accept a constant variable on every route.

PortfolioOptimisers.posdef_accepts — Function
posdef_accepts(alg, X::MatNum) -> Bool

Return true when the algorithm alg of Posdef leaves X unchanged, so posdef! returns before any repair.

Each algorithm has its own test. An algorithm of NearestCorrelationMatrix.jl accepts a matrix that passes isposdef. ClippedNearestCorrelation accepts a matrix only when its smallest correlation eigenvalue is also at least tau / 2, so it repairs a matrix that is positive definite but almost singular.

Algorithm

The method Julia selects on the type of alg is the algorithm.

  1. Any algorithm but ClippedNearestCorrelation: return isposdef(X).
  2. ClippedNearestCorrelation:
    1. Return false when a variance is exactly zero. The zero-row rule of posdef! runs next, and it repairs the block of positive variances, which this test then reads.
    2. Standardise X into C with clipped_correlation, which refuses the inputs the repair cannot read.
    3. Return the verdict of clipped_repair_holds on X and C.

Arguments

  • alg: The algorithm of Posdef.
  • X: Covariance-like or correlation-like matrix assets × assets.

Validation

Returns

  • flag::Bool: true when X is left unchanged.

Related

source
PortfolioOptimisers.posdef_repair! — Function
posdef_repair!(alg, X::MatNum; kwargs...) -> MatNum

Repair X in place under the algorithm alg of Posdef. posdef! calls it after posdef_accepts refuses X and after posdef! sets the zero variances aside, so no variance that reaches it is zero.

Algorithm

The method Julia selects on the type of alg is the algorithm.

  1. Any algorithm but ClippedNearestCorrelation, which is an algorithm of NearestCorrelationMatrix.jl:
    1. Read the diagonal of X into s. When any entry of s is not one, X is a covariance matrix. Then replace s with its square roots and convert X to a correlation matrix with StatsBase.cov2cor!. The test is any(!isone, s), so it is the value of the diagonal that decides, never the type of X.
    2. Project X onto the nearest correlation matrix with NearestCorrelationMatrix.nearest_cor!, under alg and kwargs.
    3. When step 1 converted a covariance matrix, convert X back with StatsBase.cor2cov!. The standard deviations are the ones read in step 1, so the original diagonal returns up to rounding.
    4. Check X with assert_posdef_repair, and return it.
  2. ClippedNearestCorrelation, whose # Mathematical definition states the formulas:
    1. Read the variances v and the standard deviations s, and standardise X into C with clipped_correlation.
    2. When alg.higham is true, replace C with the result of higham_alternating_projections.
    3. Take the eigen decomposition E of C.
    4. For tau equal to alg.tau and then 10 * alg.tau: clip the eigenvalues of E at tau into Y, scale the diagonal of Y to one, write S = Y .* s' .* s symmetrised into X, set the diagonal of X to v, and return X when clipped_repair_holds accepts X and Y.
    5. Check the last X with assert_posdef_repair, and return it. The clip makes a positive semidefinite matrix, so a last X with no Cholesky factor passes when its smallest eigenvalue is a round-off below zero.

Arguments

  • alg: The algorithm of Posdef.
  • X: Covariance-like or correlation-like matrix assets × assets.
  • kwargs...: The keyword arguments of NearestCorrelationMatrix.nearest_cor!. ClippedNearestCorrelation reads none, and Posdef refuses them with it.

Validation

Returns

  • X::MatNum: The input matrix X, modified in place.

Related

source
PortfolioOptimisers.clipped_correlation — Function
clipped_correlation(
    X::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}},
    v::AbstractVector{<:Union{Number, AbstractJuMPScalar}}
) -> Any

Standardise a covariance matrix into its correlation matrix, and refuse the inputs that ClippedNearestCorrelation cannot read.

The entry $C_{ij} = \Sigma_{ij} / (\sigma_i \sigma_j)$ divides by the product of the standard deviations, and the diagonal is set to one exactly. The function tests the symmetry of C and not of X, so the test does not change with the units of X. A covariance in units a thousand times smaller passes or fails as the original does.

Algorithm

  1. Refuse a non-finite entry of X with assert_all_finite.
  2. Refuse a variance that is not positive with assert_gt0.
  3. Divide X by s .* s', where s = sqrt.(v), into C, and set the diagonal of C to one.
  4. Refuse C when an entry differs from its transpose by more than 1e-8 + 1e-5 * abs(C[j, i]). The repair reads the lower triangle alone, so a larger difference is a data error and not round-off.
  5. Return C.

Arguments

  • X: Covariance-like or correlation-like matrix assets × assets.
  • v: The diagonal of X.

Validation

  • all(isfinite, X), which raises an IsNonFiniteError.
  • all(v .> 0), which raises a DomainError.
  • C symmetric to the tolerance of step 4, which raises an ArgumentError.

Returns

  • C::Matrix: The correlation matrix of X.

Related

source
PortfolioOptimisers.clipped_repair_holds — Function
clipped_repair_holds(
    alg::ClippedNearestCorrelation,
    X::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}},
    C::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}}
) -> Bool

Return true when ClippedNearestCorrelation accepts the covariance X with the correlation matrix C.

This is the acceptance test of the clip. The same test decides whether posdef_accepts leaves an input unchanged. Each factorisation reads the lower triangle alone.

Algorithm

  1. Return false when X has no Cholesky factor.
  2. Return false when the smallest eigenvalue of C is below alg.tau / 2.
  3. Return whether the smallest eigenvalue of X is positive.

Arguments

  • alg: The algorithm.
  • X: Covariance-like or correlation-like matrix assets × assets.
  • C: The correlation matrix of X.

Returns

  • flag::Bool: true when X is accepted.

Related

source
PortfolioOptimisers.assert_posdef_repair — Function
assert_posdef_repair(
    alg,
    X::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}}
)

Check that the result X of a repair under the algorithm alg of Posdef is positive semidefinite to round-off, and refuse it otherwise.

Both methods of posdef_repair! end with this check. A singular result, such as a covariance with a perfectly correlated pair, passes it, so a repair that reaches a valid covariance returns with no message. The tolerance is the one that EigenFallbackSquareRoot applies before it takes the square root, so every result that passes has a square root under the default of mtx_sqrt.

Mathematical definition

\[\begin{align} \lambda_{\min}(\mathbf{X}) &\geq -N \varepsilon \max_{i} \lvert \lambda_{i} \rvert\,. \end{align}\]

Where:

  • $\lambda_{\min}(\mathbf{X})$, $\lambda_{i}$: Smallest eigenvalue and $i$-th eigenvalue of the lower triangle of X, read as a symmetric matrix.
  • $N$: Number of rows of X.
  • $\varepsilon$: Machine epsilon of the element type, twice its unit roundoff $u$.

Algorithm

  1. Refuse X when an entry is not finite.
  2. Take the eigenvalues of the lower triangle of X, read as a symmetric matrix.
  3. Return nothing when the smallest eigenvalue is at least the tolerance of # Mathematical definition.
  4. Refuse X otherwise.

Arguments

  • alg: The algorithm of Posdef that made X. The message names it.
  • X: Covariance-like or correlation-like matrix assets × assets.

Validation

Returns

  • nothing.

Related

source
PortfolioOptimisers.higham_alternating_projections — Function
higham_alternating_projections(
    C::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}},
    iter::Integer
) -> Any

Run Higham's alternating projections with Dykstra's correction on a correlation matrix, and return the last iterate. ClippedNearestCorrelation states the iteration under # Mathematical definition.

This is Algorithm 3.3 of [24] with the unweighted Frobenius norm. The floor of 5 * eps in step 2.2 and the stop test of step 2.5 are this library's changes. The original algorithm projects with a floor of zero and states no stop test. Section 4 of that work stops on the relative change of the iterates, Equation 4.1.

The iterations stop at the first iterate that is positive semidefinite to round-off, or after iter iterations. The function returns the last iterate in both cases, and the clip that follows repairs the rest. An iterate that has not converged has a unit diagonal and a spectrum that is nearly positive semidefinite, so its clip is a valid correlation matrix, and it is nearer the input than the clip of the input alone.

Algorithm

  1. Set Y to C and the correction dS to zero.
  2. For each of at most iter iterations:
    1. Subtract dS from Y into R.
    2. Clip the eigenvalues of R at 5 * eps into Y.
    3. Set dS to Y - R.
    4. Set the diagonal of Y to one.
    5. Stop when the smallest eigenvalue of Y is at least -n * eps * max|λ|.
  3. Return Y.

Arguments

  • C: The correlation matrix.
  • iter: The largest number of iterations.

Returns

  • Y::Matrix: The last iterate, a matrix of unit diagonal.

Related

References

  • [24] N. J. Higham. Computing the nearest correlation matrix—a problem from finance. IMA Journal of Numerical Analysis 22, 329–343 (2002). Section 3.2, Algorithm 3.3, and Section 4, Equation 4.1.
source
PortfolioOptimisers.zero_variance_rows! — Function
zero_variance_rows!(
    X::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}},
    fin::AbstractVector{Bool}
) -> Any

Sets the rows and columns of the zero variances of a co-moment matrix to zero, and returns the mask of the positive variances.

A variance that is exactly zero belongs to a constant variable. A positive semidefinite matrix with a zero diagonal entry has a zero row and column, so a repair that keeps the diagonal has no other answer for that row, and no correlation exists to standardise it. The test is iszero, with no tolerance. A variance of 1e-34 is positive and stays in the block.

Mathematical definition

Every $2 \times 2$ principal minor of a positive semidefinite matrix is non-negative:

\[\begin{align} \hat{\mathbf{\Sigma}}_{ii}\,\hat{\mathbf{\Sigma}}_{jj} - \hat{\mathbf{\Sigma}}_{ij}^{2} &\geq 0\,. \end{align}\]

Where:

  • $\hat{\mathbf{\Sigma}}_{ii}$: $i$-th diagonal entry of $\hat{\mathbf{\Sigma}}$.
  • $\hat{\mathbf{\Sigma}}_{ij}$: Estimated covariance between assets $i$ and $j$.

So $\hat{\mathbf{\Sigma}}_{ii} = 0$ forces $\hat{\mathbf{\Sigma}}_{ij} = 0$ for every $j$.

Algorithm

  1. Mark each row of fin whose diagonal entry in X is exactly zero.
  2. Set every entry of X whose row or column is marked, and whose other index is in fin, to zero.
  3. Return fin without the marked rows.

Arguments

  • X: Covariance-like or correlation-like matrix assets × assets.
  • fin: The rows that the caller repairs. An entry whose row or column is outside fin is never written, so a NaN frame around the block stays as it is.

Returns

  • blk::BitVector: The rows of fin with a variance that is not zero. The caller repairs this block.

Related

source
PortfolioOptimisers.zero_variance_block! — Function
zero_variance_block!(
    f,
    X::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}}
) -> Bool

Runs a matrix verb on the block of the positive variances of X, when X has a zero variance, and writes the block back.

A zero variance has no correlation, so a verb that standardises X divides zero by zero on that row. zero_variance_rows! sets the row and column of each zero variance to zero, which is the only answer a positive semidefinite matrix has for them, and the verb then runs on the rest. posdef!, denoise! and detone! share this step.

Algorithm

  1. Set the zero-variance rows and columns of X to zero with zero_variance_rows!, and read p, the mask of the positive variances.
  2. Return false when every variance is positive. The caller then runs its verb on the whole of X.
  3. When at least one variance is positive, copy the block X[p, p], call f(block, count(p)), and write the block back into X.
  4. Return true. A matrix whose variances are all zero is the zero matrix after step 1, so f is not called.

Arguments

  • f: The verb, called as f(block, n) with the block of the positive variances and its size n. It changes block in place. The size lets a verb rescale a ratio that reads the number of assets.
  • X: Covariance-like or correlation-like matrix assets × assets.

Returns

  • done::Bool: true when X had a zero variance, so the caller returns X. false when X is unchanged and the caller runs its verb on the whole of it.

Related

source

References

[24]
N. J. Higham. Computing the nearest correlation matrix—a problem from finance. IMA Journal of Numerical Analysis 22, 329–343 (2002).