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) -> BoolReturn 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.
- Any algorithm but
ClippedNearestCorrelation: returnisposdef(X). ClippedNearestCorrelation:- Return
falsewhen a variance is exactly zero. The zero-row rule ofposdef!runs next, and it repairs the block of positive variances, which this test then reads. - Standardise
XintoCwithclipped_correlation, which refuses the inputs the repair cannot read. - Return the verdict of
clipped_repair_holdsonXandC.
- Return
Arguments
alg: The algorithm ofPosdef.X: Covariance-like or correlation-like matrixassets × assets.
Validation
ClippedNearestCorrelationrefuses whatclipped_correlationrefuses.
Returns
flag::Bool:truewhenXis left unchanged.
Related
PortfolioOptimisers.posdef_repair! — Function
posdef_repair!(alg, X::MatNum; kwargs...) -> MatNumRepair 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.
- Any algorithm but
ClippedNearestCorrelation, which is an algorithm ofNearestCorrelationMatrix.jl:- Read the diagonal of
Xintos. When any entry ofsis not one,Xis a covariance matrix. Then replaceswith its square roots and convertXto a correlation matrix withStatsBase.cov2cor!. The test isany(!isone, s), so it is the value of the diagonal that decides, never the type ofX. - Project
Xonto the nearest correlation matrix withNearestCorrelationMatrix.nearest_cor!, underalgandkwargs. - When step 1 converted a covariance matrix, convert
Xback withStatsBase.cor2cov!. The standard deviations are the ones read in step 1, so the original diagonal returns up to rounding. - Check
Xwithassert_posdef_repair, and return it.
- Read the diagonal of
ClippedNearestCorrelation, whose# Mathematical definitionstates the formulas:- Read the variances
vand the standard deviationss, and standardiseXintoCwithclipped_correlation. - When
alg.highamistrue, replaceCwith the result ofhigham_alternating_projections. - Take the eigen decomposition
EofC. - For
tauequal toalg.tauand then10 * alg.tau: clip the eigenvalues ofEattauintoY, scale the diagonal ofYto one, writeS = Y .* s' .* ssymmetrised intoX, set the diagonal ofXtov, and returnXwhenclipped_repair_holdsacceptsXandY. - Check the last
Xwithassert_posdef_repair, and return it. The clip makes a positive semidefinite matrix, so a lastXwith no Cholesky factor passes when its smallest eigenvalue is a round-off below zero.
- Read the variances
Arguments
alg: The algorithm ofPosdef.X: Covariance-like or correlation-like matrixassets × assets.kwargs...: The keyword arguments ofNearestCorrelationMatrix.nearest_cor!.ClippedNearestCorrelationreads none, andPosdefrefuses them with it.
Validation
- The repaired
Xis positive semidefinite to round-off, which raises aPosdefRepairErrorthroughassert_posdef_repair.
Returns
X::MatNum: The input matrixX, modified in place.
Related
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
- Refuse a non-finite entry of
Xwithassert_all_finite. - Refuse a variance that is not positive with
assert_gt0. - Divide
Xbys .* s', wheres = sqrt.(v), intoC, and set the diagonal ofCto one. - Refuse
Cwhen an entry differs from its transpose by more than1e-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. - Return
C.
Arguments
X: Covariance-like or correlation-like matrixassets × assets.v: The diagonal ofX.
Validation
all(isfinite, X), which raises anIsNonFiniteError.all(v .> 0), which raises aDomainError.Csymmetric to the tolerance of step 4, which raises anArgumentError.
Returns
C::Matrix: The correlation matrix ofX.
Related
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
- Return
falsewhenXhas no Cholesky factor. - Return
falsewhen the smallest eigenvalue ofCis belowalg.tau / 2. - Return whether the smallest eigenvalue of
Xis positive.
Arguments
alg: The algorithm.X: Covariance-like or correlation-like matrixassets × assets.C: The correlation matrix ofX.
Returns
flag::Bool:truewhenXis accepted.
Related
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
- Refuse
Xwhen an entry is not finite. - Take the eigenvalues of the lower triangle of
X, read as a symmetric matrix. - Return
nothingwhen the smallest eigenvalue is at least the tolerance of# Mathematical definition. - Refuse
Xotherwise.
Arguments
alg: The algorithm ofPosdefthat madeX. The message names it.X: Covariance-like or correlation-like matrixassets × assets.
Validation
all(isfinite, X), which raises aPosdefRepairError.- The inequality of
# Mathematical definition, which raises aPosdefRepairError.
Returns
nothing.
Related
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
- Set
YtoCand the correctiondSto zero. - For each of at most
iteriterations:- Subtract
dSfromYintoR. - Clip the eigenvalues of
Rat5 * epsintoY. - Set
dStoY - R. - Set the diagonal of
Yto one. - Stop when the smallest eigenvalue of
Yis at least-n * eps * max|λ|.
- Subtract
- 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.
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
- Mark each row of
finwhose diagonal entry inXis exactly zero. - Set every entry of
Xwhose row or column is marked, and whose other index is infin, to zero. - Return
finwithout the marked rows.
Arguments
X: Covariance-like or correlation-like matrixassets × assets.fin: The rows that the caller repairs. An entry whose row or column is outsidefinis never written, so aNaNframe around the block stays as it is.
Returns
blk::BitVector: The rows offinwith a variance that is not zero. The caller repairs this block.
Related
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
- Set the zero-variance rows and columns of
Xto zero withzero_variance_rows!, and readp, the mask of the positive variances. - Return
falsewhen every variance is positive. The caller then runs its verb on the whole ofX. - When at least one variance is positive, copy the block
X[p, p], callf(block, count(p)), and write the block back intoX. - Return
true. A matrix whose variances are all zero is the zero matrix after step 1, sofis not called.
Arguments
f: The verb, called asf(block, n)with the block of the positive variances and its sizen. It changesblockin place. The size lets a verb rescale a ratio that reads the number of assets.X: Covariance-like or correlation-like matrixassets × assets.
Returns
done::Bool:truewhenXhad a zero variance, so the caller returnsX.falsewhenXis unchanged and the caller runs its verb on the whole of it.
Related
References
- [24]
- N. J. Higham. Computing the nearest correlation matrix—a problem from finance. IMA Journal of Numerical Analysis 22, 329–343 (2002).