Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 205 / 5 / c

Solution

For the active set

A_{k}

, maintain

M_{k}^{- 1} = (X_{A_{k}} X_{A_{k}}^{T} + λ I)^{- 1} .

The initial

n \times n

O (n^{3})

. At step

k

, compute

v_{k} = M_{k}^{- 1} Y

O (n^{2})

operations and all active ridge coefficients

X_{A_{k}}^{T} v_{k}

O (∣ A_{k} ∣ n)

operations; their smallest absolute value determines

j_{k}

After deleting

j_{k}

M_{k + 1} = M_{k} - X_{j_{k}} X_{j_{k}}^{T} .

Part b ensures that the denominator in the Sherman–Morrison formula is positive, and the rank-one downdate

M_{k + 1}^{- 1} = M_{k}^{- 1} + \frac{M _{k}^{- 1} X _{j_{k}} X _{j_{k}}^{T} M _{k}^{- 1}}{1 - X _{j_{k}}^{T} M _{k}^{- 1} X _{j_{k}}}

costs

O (n^{2})

. Summing over the

p

steps gives

O (n^{3}) + O (p n^{2}) + O (n \sum_{k = 1}^{p} ∣ A_{k} ∣) = O (n^{3} + p n^{2} + p^{2} n) .

Since

p \geq n

, both earlier terms are bounded by

O (p^{2} n)

, proving the claimed computational complexity within computational complexity theory.

There are no discussions about this article yet.

There are currently no matching articles.