Doubts about OKVS: Why not deal with the submatrix A D E of matrix T?

[qxzhou1010]

In the page-6 of the RR22 paper, here is a statement: "Since all of T^* is lower triangular, we can compute P^*". Therefore, we have completed the solution of vector P and the encoding process of OKVS.

But I am very puzzled about this. In T^* we did not explicitly handle submatrix A^*, D,E . Why can we simply say that T^* is a lower triangular matrix? If these submatrixes (A^*, D,E) are not lower triangular matrices, it seems that we cannot solve vector P through back-substitution?

[ladnir]

A doesn't matter. It can be anything. What matters is that B and F are lower triangular.

The positions corresponding to A* can be set to anything, e.g. 0. What's left is the system

B* 0 E F

The first row of B* has not dependencies and so you can simple set it to the value you want. The next row might depend on the previous but no others. So set that according. This is just back substitution...

[qxzhou1010]

Thank you for your prompt response. I understand your explanation.

If we focus only on the system:

$B^*$ 0 E F

we can easily solve for the corresponding values in the vector 𝑃 using back substitution.

However, this system only has $\hat m + \delta$ columns.

Since the size of the vector 𝑃 is 𝑚 and obviously $m > \hat m + \delta$ , how should we solve for the remaining values in 𝑃 (specifically, the $m-\hat m - \delta$ values )?

Note that you said "The positions corresponding to A* can be set to anything, e.g. 0.". Can this be understood as simply considering the value of the corresponding position in $P$ as 0 ?

[ladnir]

yes, the positions of p that you don't actually use can just be 0. So p might be 20% zeros.

[qxzhou1010]

Thanks very much. I totally understand this problem.