# Linear Computation Coding: A Framework for Joint Quantization and Computing
## 5 Performance Analysis
### Total Number of Additions  
The exponential aspect ratio has the following impact on the trade-off between distortion and computational cost: For \(K+S_{\ell}\) choices from the codebook, the wiring matrix \(\mathbf{W}_{\ell}\) contains \(K+S_{\ell}\) nonzero signed digits according to approximation (20). Due to the columnwise decomposition, these are \(1+S_{\ell}/K\) of them per column. At this point, we must distinguish between wide and tall matrices.  
**Wide Matrices:**: For the number of additions, the number of nonzero signed digits per _row_ is relevant, as each row of \(\mathbf{W}_{\ell}\) is multiplied to an input vector \(x\) when calculating the product \(h=\mathbf{W}_{\ell}x\). For the standard choice of square wiring matrices, the counting per column versus counting per row hardly makes a difference on average. Though they may vary from row to row, the total number of additions is approximately equal to \(S_{\ell}\).
**Tall Matrices:**: The transposition converts the columns into rows. Thus, \(S_{\ell}\) is exactly the number of additions.  
In order to approximate an \(N\times K\) target matrix \(\mathbf{T}\) with \(N=\frac{1}{R}\log_{2}K=\mathsf{O}(\log K)\) rows, we need approximately \(S_{\ell}\) additions. For any desired distortion \(D\), the computational cost of the product \(\mathbf{W}_{\ell}x\) is by a factor \(\mathsf{O}(\log K)\) smaller than the number of entries in the target matrix. This is the same scaling as in the mailman algorithm. Given such a scaling, the mailman algorithm allows for a fixed distortion \(D\), which depends on the size of the target matrix. The proposed algorithm, however, can achieve arbitrarily low distortion by setting \(S_{\ell}\) appropriately large, regardless of the matrix size.  
Computations are also required for the codebook matrix. All three codebook matrices discussed in Section 4.4 require at most \(K\) and \(2K\) additions for tall and wide matrices, respectively. Adding the computational costs of wiring and codebook matrices, we obtain  
\[C\approx vK+\sum_{\ell=1}^{L}S_{\ell}K=(S+v)K \tag{41}\]  
with \(S=\sum_{\ell=1}^{L}S_{\ell}\) and  
\[v=\begin{cases}1&\text{for tall matrices}\\ 2&\text{for wide matrices}\end{cases}. \tag{42}\]  
Figure 3: \(R\)th root of median total squared error vs. the number of columns \(K\) in logarithmic scale for various rates \(R\).  
Normalizing to the number of elements of the \(N\times K\) target matrix \(\mathbf{T}\), we have  
\[\tilde{C}=\frac{C}{KN}\approx\frac{S+v}{N}. \tag{43}\]  
The computational cost per matrix entry vanishes with increasing matrix size. This behavior fundamentally differs from state-of-the-art methods discussed in Examples 1 and 2, where the matrix size has no impact on the computational cost per matrix entry.  
There are slightly less overall additions required, if a \(K\times K\) square matrix is cut into tall submatrices than if it is cut into wide submatrices. Although the vertical cut requires \(K/N\) surplus additions due to (10), it saves approximately \(K\) additions due to (41) in comparison to the horizontal cut.