iheartla / Iheartla.github.io

0 stars 0 forks source link

convex_optimization_680 incorrect assumption of sizes #2

Open pressureless opened 3 years ago

pressureless commented 3 years ago

Create by @alecjacobson :

The example in convex_optimization_680 assumes all matrices are 4x4. Part of this assumption is that the P₁,P₂,P₃ matrices are all the same size and can be captured as a sequence-of-same-size matrices and hence ₁,₂,₃ are unicode subscripts filling in _i. According to the source, we should not think of the P matrices as coming such a sequence, rather they're all just (square) permutation matrices (hence P) and the subscript is a mark to differentiation them. In particular P₃ does not need to be the same size as P₁,P₂.

Ideally we could translate this example as:

[P₁  0
 0     P₃][    L            0
             P₃ᵀCP₂ᵀU⁻¹  -L̃][U  L⁻¹P₁ᵀB
                                     0        Ũ   ][P₂   0
                                                       0    I_n]
where

P₁ ∈ ℝ^(m×m) 
P₂ ∈ ℝ^(m×m) 
P₃ ∈ ℝ^(n×n) 
B ∈ ℝ^(m×n) 
C ∈ ℝ^(n×m) 
L ∈ ℝ^(m×m) 
L̃ ∈ ℝ^(n×n) 
U ∈ ℝ^(m×m) 
Ũ ∈ ℝ^(n×n)

Because of bugs pressureless/linear_algebra#4 and pressureless/linear_algebra#71 this will not work currently.

In the meantime, we could at least not use 4s for all dimensions and protect the Ps with backticks

[`P₁`  0
 0     `P₃`][    L            0
             `P₃`ᵀC`P₂`ᵀU⁻¹  -L̃][U  L⁻¹`P₁`ᵀB
                                             0        Ũ   ][`P₂`   0
                                                                   0    I₇]

where

`P₁` ∈ ℝ^(4×4) 
`P₂` ∈ ℝ^(4×4) 
`P₃` ∈ ℝ^(7×7) 
  B ∈ ℝ^(4×7) 
  C ∈ ℝ^(7×4) 
  L ∈ ℝ^(4×4) 
  L̃ ∈ ℝ^(7×7) 
  U ∈ ℝ^(4×4) 
  Ũ ∈ ℝ^(7×7)
pressureless commented 3 years ago

Comment by @alecjacobson :

This appears to at least be producing output without error:

[`P₁`  0
 0     `P₃`][    L               0
             `P₃`ᵀC`P₂`ᵀU⁻¹  -L̃][U  L⁻¹`P₁`ᵀB
                                              0        Ũ   ][`P₂`   0
                                                                   0    I_n]

where

`P₁` ∈ ℝ^(m×m) 
`P₂` ∈ ℝ^(m×m) 
`P₃` ∈ ℝ^(n×n) 
  B ∈ ℝ^(m×n) 
  C ∈ ℝ^(n×m) 
  L ∈ ℝ^(m×m) 
  L̃ ∈ ℝ^(n×n) 
  U ∈ ℝ^(m×m) 
  Ũ ∈ ℝ^(n×n)