Cross-Sectional Factorisation: private API

Functions

PortfolioOptimisers.cross_sectional_leverage_one — Function
cross_sectional_leverage_one(
    A::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}},
    w::AbstractVector{<:Union{Number, AbstractJuMPScalar}},
    intercept::Bool;
    D,
    F,
    G
) -> BitVector

Return the mask of the eligible assets of one observation whose leverage in the weighted design is one.

The leverage of row $i$ is the diagonal entry $h_{i}$ of the projection onto the column span of the design. It is one exactly when the design gives the row a direction of its own, for example when the row is the only member of a level of a one-hot family. A least-squares fit then reproduces the target of that row whatever it is, so its residual is zero by construction and its variance under the design is zero too. The mask does not depend on the scale of the target, and it does not depend on a positive weight either, because a positive weight moves no row into or out of the span of the others.

Mathematical definition

\[\begin{align} \mathbf{D} \mathbf{\Pi} &= \mathbf{Q} \mathbf{R}\,, & \mathbf{Q}_{1} &= \mathbf{D} \mathbf{\Pi}_{1} \mathbf{R}_{11}^{-1}\,, \\ h_{i} &= \sum_{j = 1}^{r} \left(Q_{1}\right)_{ij}^{2} + \mathbb{1}_{\text{intercept}} \frac{w_{i}}{\sum_{k} w_{k}}\,, & \text{mark}_{i} &= 1 - h_{i} \le \sqrt{\epsilon}\,. \end{align}\]

Where:

  • $\mathbf{D}$: Weighted design sqrt.(w) .* A.
  • $\mathbf{\Pi}$, $\mathbf{Q}$, $\mathbf{R}$: Column permutation, orthonormal factor and triangular factor of the column-pivoted QR of $\mathbf{D}$.
  • $r$: Numerical rank of the design, read as cross_sectional_rank reads it.
  • $\mathbf{\Pi}_{1}$, $\mathbf{R}_{11}$, $\mathbf{Q}_{1}$: The first r columns of $\mathbf{\Pi}$, the leading r × r block of $\mathbf{R}$, and the first r columns of $\mathbf{Q}$.
  • $h_{i}$: Leverage of row $i$.
  • $w_{i}$: Weight of row $i$.
  • $\epsilon$: Machine epsilon of the element type of $\mathbf{R}$.

The intercept puts the column sqrt.(w) in front of the design. Under intercept, A is centred on its weighted means, so every column of $\mathbf{D}$ is orthogonal to sqrt.(w), and the two spans add. The projection onto sqrt.(w) gives each row $w_{i} / \sum_{k} w_{k}$, and the projection onto the span of $\mathbf{D}$ gives the rest.

The tolerance $\sqrt{\epsilon}$ absorbs the round-off of $h_{i}$, which is of order $m \epsilon$ for $m$ rows. A row whose leverage is below one by more than that keeps a residual variance that the data can estimate.

The triangular solve for $\mathbf{Q}_{1}$ costs about a quarter of the flops of forming $\mathbf{Q}_{1}$ from the reflectors of the factorisation, and it loses about $\kappa(\mathbf{R}_{11}) \epsilon$ of $h_{i}$. The ratio $|R_{11} / R_{rr}|$ estimates that condition number. When the ratio is above $\epsilon^{-1/4}$, the loss can come near the tolerance of the mark, so the verb forms $\mathbf{Q}_{1}$ from the reflectors instead.

Algorithm

  1. Take the column-pivoted QR of the weighted design D, unless the caller passes it, through cross_sectional_qr. Read the numerical rank r of D off its triangular factor through cross_sectional_rank, which answers zero for a design with no row or no column.
  2. At rank zero, take a leverage of zero on every row. Otherwise take $\mathbf{Q}_{1}$ by the triangular solve, or from the reflectors when the ratio of the diagonal of $\mathbf{R}_{11}$ is above $\epsilon^{-1/4}$, and sum the squares of each row, giving the leverage h.
  3. When intercept is true, add w ./ sum(w) to h.
  4. Mark each row whose 1 - h is at most sqrt(eps).

Arguments

  • A::MatNum: Exposures of the eligible assets, eligible assets × factors, already demeaned when an intercept is fitted.
  • w::VecNum: Cross-sectional weights of the eligible assets.
  • intercept::Bool: Whether the fit has an intercept.
  • D::MatNum: Weighted design sqrt.(w) .* A. A caller that weighted the design already passes it.
  • F: Column-pivoted QR of D, or nothing to take it here. The regression passes the factorisation that its solve reads, so the design is factorised once.
  • G: A buffer with the rows and at least the columns of D that receives the pivoted columns of the triangular solve, or nothing to gather them into a new matrix. The regression passes a buffer of its task.

Returns

  • mark::BitVector: Leverage-one mask, one entry per eligible asset.

Related

source
PortfolioOptimisers.cross_sectional_leverage — Function
cross_sectional_leverage(
    D::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}},
    F,
    r::Integer;
    G
) -> AbstractVector{<:Union{Number, AbstractJuMPScalar}}

Return the leverage of each row of a weighted design in the span of its columns, read off the column-pivoted QR of the design.

cross_sectional_leverage_one states the definition, the triangular solve and the guard on the condition number.

Arguments

  • D::MatNum: Weighted design of one observation, eligible assets × factors.
  • F: Column-pivoted QR of D.
  • r::Integer: Numerical rank of D, read by cross_sectional_rank.
  • G: A buffer for the pivoted columns, or nothing, as cross_sectional_leverage_one states.

Returns

  • h::VecNum: Leverage of each row, zero on every row at rank zero.

Related

source
PortfolioOptimisers.cross_sectional_pivot_columns — Function
cross_sectional_pivot_columns(G::Nothing, D::MatNum, p::AbstractVector{<:Integer}) -> MatNum
cross_sectional_pivot_columns(G::MatNum, D::MatNum, p::AbstractVector{<:Integer}) -> MatNum

Return the columns p of the weighted design D as a matrix of its own, which cross_sectional_leverage divides in place.

Algorithm

The method that Julia selects is the algorithm.

  1. No buffer: gather the columns into a new matrix, D[:, p].
  2. A buffer: copy the columns into its first length(p) columns, and return that view. A loop over observations then gathers into one allocation.

Arguments

  • G: A buffer with the rows of D and at least length(p) columns, or nothing.
  • D::MatNum: Weighted design of one observation, eligible assets × factors.
  • p::AbstractVector{<:Integer}: The pivoted columns of the leading block of the QR of D.

Returns

  • Dp::MatNum: The columns p of D, eligible assets × length(p).

Related

source
PortfolioOptimisers.cross_sectional_leverage_rows — Function
cross_sectional_leverage_rows(
    cre::Union{CrossSectionalLinearRegression, CrossSectionalTargetRegression},
    X::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}}
) -> Union{Nothing, Matrix{Bool}, var"#s3888"} where var"#s3888"<:Matrix{Bool}

Return the leverage-one mask that the fits of the observations write, or nothing when the estimator runs no leverage check.

A BitMatrix packs 64 entries into one word, so two threads that write rows of one word would race. So the mask is a Matrix{Bool}, whose entries are bytes, and the regression packs it after the loop through cross_sectional_bit_mask.

Arguments

  • cre: Cross-sectional regression estimator, whose leverage field decides.
  • X::MatNum: Asset returns matrix observations × assets, which gives the size of the mask.

Returns

  • h1::Option{<:Matrix{Bool}}: All false, observations × assets, or nothing.

Related

source
PortfolioOptimisers.cross_sectional_mark_leverage! — Function
cross_sectional_mark_leverage!(h1::Nothing, A::MatNum, w::VecNum, intercept::Bool,
                               t::Integer, idx::AbstractVector; D, F) -> Nothing
cross_sectional_mark_leverage!(h1::AbstractMatrix{Bool}, A::MatNum, w::VecNum,
                               intercept::Bool, t::Integer, idx::AbstractVector;
                               D::MatNum, F) -> Nothing

Mark the eligible assets of leverage one of observation t in its row of h1.

Algorithm

The method that Julia selects is the algorithm.

  1. nothing: the fit runs no leverage check, so mark nothing.
  2. A mask: write cross_sectional_leverage_one of the observation, on the factorisation F of the weighted design D, into the entries idx of the row t.

Arguments

  • h1: Leverage-one mask observations × assets, written in place, or nothing.
  • A::MatNum: Exposures of the eligible assets, eligible assets × factors, already demeaned when an intercept is fitted.
  • w::VecNum: Cross-sectional weights of the eligible assets.
  • intercept::Bool: Whether the fit has an intercept.
  • t::Integer: Row of the observation in h1.
  • idx::AbstractVector: Columns of the eligible assets in h1.
  • D::MatNum: Weighted design sqrt.(w) .* A.
  • F: Column-pivoted QR of D, as cross_sectional_shared_qr returns it.
  • G: A buffer for the pivoted columns, or nothing, as cross_sectional_leverage_one states.

Returns

  • nothing.

Related

source
PortfolioOptimisers.cross_sectional_zero_marked! — Function
cross_sectional_zero_marked!(eps::MatNum, h1::Nothing, ls::Bool) -> Nothing
cross_sectional_zero_marked!(eps::MatNum, h1::AbstractMatrix{Bool}, ls::Bool) -> Nothing

Write an exact zero into the residual of every pair that h1 marks, when the fit is a least-squares fit.

The fit reproduced the return of a marked pair, so zero is its residual in exact arithmetic, and the subtraction leaves only its round-off. A fit that is not least squares keeps the residual of a marked pair, and only marks it.

Algorithm

The method that Julia selects is the algorithm.

  1. nothing: the fit marks no pair, so change nothing.
  2. A mask: when ls is true, write zero at every marked pair.

Arguments

  • eps::MatNum: Residual matrix observations × assets, changed in place.
  • h1: Leverage-one mask of the fit, or nothing.
  • ls::Bool: cross_sectional_least_squares of the estimator.

Returns

  • nothing.

Related

source
PortfolioOptimisers.cross_sectional_qr — Function
cross_sectional_qr(D::MatNum, F::Nothing) -> LinearAlgebra.QRPivoted
cross_sectional_qr(D::MatNum, F) -> typeof(F)
cross_sectional_qr(D::MatNum, F::Nothing, Q::MatNum) -> LinearAlgebra.QRPivoted

Return the column-pivoted QR of the weighted design D, or the factorisation F that the caller already took.

The leverage check, the solve and the mark of the dropped columns of one observation read one factorisation. The first reader that runs takes it, and every later reader receives it.

LinearAlgebra.qr copies D into a new matrix and factorises the copy in place. With a buffer Q, the method copies D into Q and factorises Q in place, which is the same computation, so a loop over observations factorises into one allocation.

Arguments

  • D::MatNum: Weighted design of one observation, eligible assets × factors.
  • F: Column-pivoted QR of D, or nothing.
  • Q::MatNum: A buffer of the size and the element type of D, which receives the factors. The factorisation reads it until the caller writes it again.

Returns

  • F: LinearAlgebra.qr(D, LinearAlgebra.ColumnNorm()), or the factorisation that the caller passed.

Related

source
PortfolioOptimisers.cross_sectional_gram_factor — Function
cross_sectional_gram_factor(D::MatNum, gram = nothing) -> Option{<:LinearAlgebra.CholeskyPivoted}
cross_sectional_gram_factor(D::StridedMatrix{T}, gram::Matrix{T}) where {T <: LinearAlgebra.BlasFloat}
    -> Option{<:LinearAlgebra.CholeskyPivoted}

Return the pivoted Cholesky factorisation of the Gram matrix of a weighted design, or nothing when NormalEquationsSolve must not solve the normal equations of the design.

The verb passes the factorisation when it has full rank and cross_sectional_gram_conditioned estimates a condition number of the triangular factor of at most $\epsilon^{-1/4}$. The condition number of the Gram matrix is the square of the condition number of the design, so the normal equations keep about half of the digits of the element type.

LinearAlgebra.cholesky factorises a copy of the Gram matrix. With a buffer gram of the element type of a design of BLAS type, the verb forms the Gram matrix in the buffer and factorises it there, which is the same computation, so a loop over observations allocates neither matrix.

Algorithm

  1. Return nothing for a design with no row or no column.
  2. Form the Gram matrix G = D' * D, in gram when it is a buffer of the element type of D and D is of BLAS type, and take its factorisation with LinearAlgebra.RowMaximum() and the tolerance sqrt(eps) * maximum(diag(G)) on the pivots, in place in that buffer. A pivot is the square of a diagonal entry of the factor, so the tolerance bounds the ratio of the entries by $\epsilon^{-1/4}$.
  3. Return the factorisation when cross_sectional_gram_conditioned passes it, and nothing otherwise.

Arguments

  • D::MatNum: Weighted design of one observation, eligible assets × factors.
  • gram: A factors × factors buffer, overwritten with the factor, or nothing.

Returns

  • C::Option{<:LinearAlgebra.CholeskyPivoted}: The factorisation, or nothing.

Related

source
PortfolioOptimisers.cross_sectional_gram_conditioned — Function
cross_sectional_gram_conditioned(C::LinearAlgebra.CholeskyPivoted, K::Integer) -> Bool

Return true when NormalEquationsSolve can solve the normal equations through the pivoted Cholesky factorisation C of the Gram matrix of a design of K columns.

The test is the estimate of the condition number of the triangular factor $\mathbf{U}$ in the 1-norm, which LinearAlgebra.cond takes from LAPACK.trcon! for a BLAS type and computes from the inverse for every other type. The condition number of $\mathbf{U}$ in the 2-norm is the condition number of the design. The two norms differ by a factor of at most $K$, so the test bounds the condition number of the design by about $K \epsilon^{-1/4}$. The ratio of the pivots alone is not the test, because it can be far below the condition number. A 1600 × 28 design built on a Kahan matrix has a condition number of 3.2e7 and a ratio of the pivots of 385, and its normal equations lose all but two digits.

Algorithm

  1. Return false when the rank of C is less than K, so the estimate never reads a factor that the factorisation did not finish.
  2. Return true when the estimate is at most $\epsilon^{-1/4}$ of the element type of C, and false otherwise.

Arguments

  • C::LinearAlgebra.CholeskyPivoted: Pivoted Cholesky factorisation of the Gram matrix of a weighted design.
  • K::Integer: Column count of the design.

Returns

  • ok::Bool: true when the normal equations of the design keep at least about half of the digits of the element type.

Related

source
PortfolioOptimisers.cross_sectional_normal_solve — Function
cross_sectional_normal_solve(C, A::MatNum, y::VecNum, v) -> VecNum

Return the answer of the normal equations of a weighted design through the pivoted Cholesky factorisation of its Gram matrix, C \ (A' * y).

C \ (A' * y) forms A' * y in a new vector and solves on a copy of it. With a buffer v of the element type of a factorisation of BLAS type, the verb takes the same steps in v, so the answer has the same bits and a loop over observations forms the right side into one allocation.

Algorithm

The method that Julia selects is the algorithm.

  1. No buffer, or one of another element type: return C \ (A' * y).
  2. A buffer: write A' * y into v, solve in place with LinearAlgebra.ldiv!, and return a copy of v.

Arguments

  • C: Pivoted Cholesky factorisation of A' * A, as cross_sectional_gram_factor returns it.
  • A::MatNum: Weighted design of one observation, eligible assets × factors.
  • y::VecNum: Weighted target of the observation.
  • v: A buffer of length size(A, 2), overwritten, or nothing.

Returns

  • f::VecNum: Factor returns of the observation, of length size(A, 2).

Related

source
PortfolioOptimisers.cross_sectional_full_solve — Function
cross_sectional_full_solve(F, A::MatNum, y::VecNum,
                           b::Option{<:AbstractVector} = nothing) -> VecNum
cross_sectional_full_solve(F::LinearAlgebra.QRPivoted{T, <:StridedMatrix}, A::MatNum,
                           y::AbstractVector{T}, b::Vector{T}) where {T <: LinearAlgebra.BlasFloat}
    -> VecNum

Return the least-squares answer of a weighted design of full rank, through the column-pivoted QR that the caller already took.

A \ y factorises a design that is not square through LinearAlgebra.qr(A, LinearAlgebra.ColumnNorm()), so the solve through F is the same computation with no second factorisation. A square design takes A \ y, which factorises it by LU, so the answer is the one that A \ y gives on every shape.

F \ y copies y into a new work vector and solves in place on it. With a work vector b of the element type of F and y, the solve takes the same steps in b, so the answer has the same bits and a loop over observations allocates the work vector once.

Algorithm

The method that Julia selects is the algorithm.

  1. No work vector, or one whose element type differs from that of F or y: return A \ y on a square design and F \ y otherwise.
  2. A work vector of the element type of a column-pivoted QR of BLAS type: on a square design return A \ y. Otherwise zero the entries of b past size(A, 1) up to size(A, 2), copy y into its first entries, solve in place with LinearAlgebra.ldiv!, and return the first size(A, 2) entries.

Arguments

  • F: Column-pivoted QR of A, as LinearAlgebra.qr(A, LinearAlgebra.ColumnNorm()) returns it.
  • A::MatNum: Weighted design of one observation, eligible assets × factors, of full rank.
  • y::VecNum: Weighted target of the observation.
  • b: A work vector of length at least max(size(A)...), overwritten, or nothing.

Returns

  • f::VecNum: Factor returns of the observation, of length size(A, 2).

Related

source
PortfolioOptimisers.assert_cross_sectional_rank — Function
assert_cross_sectional_rank(
    D::AbstractMatrix{<:Union{Number, AbstractJuMPScalar}},
    t::Integer;
    R
)

Refuse the weighted design of one observation when its rank falls short of its factor count.

RankDeficiencyRefusal reads it under both cross-sectional regression estimators, so the two refuse the same observation with the same message.

Arguments

  • D::MatNum: Weighted design of one observation, eligible assets × factors.
  • t::Integer: Index of the observation, named by the refusal.
  • R::MatNum: Triangular factor of the column-pivoted QR of D. A caller that solves through the factorisation passes it, so the design is factorised once.

Validation

  • cross_sectional_rank of D equals size(D, 2). The ArgumentError names the observation, the rank, the factor count and the count of eligible assets.

Returns

  • nothing.

Related

source
PortfolioOptimisers.cross_sectional_shared_qr — Function
cross_sectional_shared_qr(h1::Nothing, dc::Nothing,
                          alg::AbstractCrossSectionalSolveAlgorithm, D::MatNum,
                          Q::MatNum) -> Nothing
cross_sectional_shared_qr(h1::Nothing, dc::Nothing,
                          alg::Union{UncheckedSolve, MinimumNormSolve,
                                     PseudoInverseFallback, RankDeficiencyRefusal,
                                     DependentColumnDrop}, D::MatNum,
                          Q::MatNum) -> LinearAlgebra.QRPivoted
cross_sectional_shared_qr(h1, dc, alg::AbstractCrossSectionalSolveAlgorithm, D::MatNum,
                          Q::MatNum) -> LinearAlgebra.QRPivoted

Return the column-pivoted QR that every reader of one observation shares, or nothing when no reader of the regression needs it.

The leverage check writes h1, and the mark of the dropped columns of DependentColumnDrop writes dc. Both read a QR of the weighted design, so the regression takes it once and hands it to the solve as well. With neither mask, the regression takes it for a member of the library whose solve reads a QR, so that it factorises into the buffer of its task. NormalEquationsSolve reads none, and a member of a caller ignores it, so both receive nothing.

Algorithm

The method that Julia selects is the algorithm.

  1. Both masks are nothing, and the member reads no QR: return nothing.
  2. Otherwise: return cross_sectional_qr of D into the buffer Q.

Arguments

  • h1: The leverage-one mask of the fit, or nothing when the fit runs no leverage check.
  • dc: The dropped-column mask of the fit, or nothing.
  • alg: The solve algorithm of the estimator.
  • D::MatNum: Weighted design of one observation, eligible assets × factors.
  • Q::MatNum: A buffer of the size and the element type of D, which receives the factors. The factorisation reads it until the next observation of the task writes it.

Returns

  • F::Option{<:LinearAlgebra.QRPivoted}: The factorisation, or nothing.

Related

source
PortfolioOptimisers.leverage_one_nan — Function
leverage_one_nan(h1::Nothing, A::MatNum) -> MatNum
leverage_one_nan(h1::AbstractMatrix{Bool}, A::MatNum) -> MatNum

Return a history of a cross-sectional fit with NaN at every pair whose leverage is one.

A pair that h1 marks gives no observation of its idiosyncratic return. The fit reproduced its return, so its residual is zero by construction, and so is the variance that reads that residual. A reader that treats such a pair as data reads the design, not the asset. The function writes NaN over the pair, so every reader that skips a value that is not finite leaves the pair out. It never changes A.

Algorithm

The method that Julia selects is the algorithm.

  1. nothing: a regression built by hand states no mask, so return A.
  2. A mask: check its size, and return A when it marks no pair. Otherwise copy A into the type of a square root of its elements, which holds a NaN and the division the readers take, and write NaN at every marked pair.

Arguments

  • h1: The leverage-one mask of CrossSectionalRegression, observations × assets, or nothing.
  • A: A history on the axes of h1, observations × assets.

Validation

  • size(h1) == size(A). Raises a DimensionMismatch.

Returns

  • A::MatNum: A itself when no pair is marked, otherwise a copy with NaN at every marked pair.

Examples

julia> PortfolioOptimisers.leverage_one_nan(BitMatrix([0 1; 0 0]), [0.1 0.0; 0.3 0.4])2×2 Matrix{Float64}: 0.1  NaN 0.3    0.4

Related

source
PortfolioOptimisers.cross_sectional_least_squares — Function
cross_sectional_least_squares(cre::CrossSectionalLinearRegression) -> Bool
cross_sectional_least_squares(cre::CrossSectionalTargetRegression) -> Bool
cross_sectional_least_squares(tgt::LinearModel) -> Bool
cross_sectional_least_squares(tgt::GeneralisedLinearModel) -> Bool
cross_sectional_least_squares(tgt::AbstractRegressionTarget) -> Bool

Return whether the fit of a cross-sectional regression reproduces the return of a pair whose leverage is one.

cross_sectional_regression writes an exact zero residual at such a pair when this answers true. A least-squares fit projects the returns onto the span of the design, so the pair's residual is zero in exact arithmetic, and the subtraction leaves only its round-off. A generalised linear model with an identity link solves its score equations with the pair's own parameter, which also fits the pair exactly. Under any other link the fit reproduces the mean of the pair on the scale of the link, so the residual on the scale of the returns is not zero, and the verb answers false. So does a target the verb does not know.

Arguments

Returns

  • ls::Bool: true when the residual of a leverage-one pair is zero by construction.

Related

source