# Linear Computation Coding: A Framework for Joint Quantization and Computing
## 2 Computation Coding for General Functions  
The approximation by an artificial neural network is the current state-of-the-art to compute a multi-dimensional function efficiently. There may be other ones, yet undiscovered, as well. Thus, we define computation coding for general multi-dimensional functions. Subsequently, we discuss the practically important case of linear functions, i.e., matrix-vector products, in greater detail.  
The best starting point to understand general computation coding is rate-distortion theory in lossy data compression. In fact, computation coding can be interpreted as a lossy encoding of functions with a side constraint on the computational cost of the decoding algorithm. As we will see in the sequel, it shares a common principle with lossy source coding: Random codebooks, if suitably constructed, usually perform well.  
Computation coding consists of _computation encoding_ and _computation decoding_. Roughly speaking, computation encoding is used to find an approximate representation \(m(x)\) for a given and known function \(f(x)\) such that \(m(x)\) can be calculated for most arguments \(x\) in some support \(\mathcal{X}\) with low computational cost and \(m(x)\) approximates \(f(x)\) with high accuracy. Computation decoding is the calculation of \(m(x)\). Formal definitions are as follows:  
**Definition 1**.: _Given a probability space \((\mathcal{X},P_{\mathcal{X}})\) and a metric \(d:\mathcal{F}\times\mathcal{F}\mapsto\mathbb{R}\), a computation encoding with distortion \(D\) for given function \(f:\mathcal{X}\mapsto\mathcal{F}\) is a mapping \(m:\mathcal{X}\mapsto\mathcal{M}\subseteq\mathcal{F}\) such that \(\operatorname{\mathbb{E}}_{x\in\mathcal{X}}[d(f(x),m(x))]\leq D\)._  
**Definition 2**.: _A computation decoding with computational cost \(C\) for given operator \(\mathsf{C}\) is an implementation of the mapping \(m:\mathcal{X}\mapsto\mathcal{M}\) such that \(\mathsf{C}[m(x)]\leq C\) for all \(x\in\mathcal{X}\)._  
The computational cost operator \(\mathsf{C}[m(\cdot)]\) measures the cost to implement the function \(m(\cdot)\). It reflects the properties of the hardware that executes the computation.  
Computation coding can be regarded as a generalization of lossy source coding. If we consider the identity function \(f(x)=x\) and the limit \(C\to\infty\), computation coding reduces to lossy source coding with \(m(x)\) being the codeword for \(x\). Rate-distortion theory analyzes the trade-off between distortion \(D\) and the number of distinct codewords. In computation coding, we are interested in the trade-off between distortion \(D\) and computational cost \(C\). The number of distinct codewords is of no or at most subordinate concern.  
The expectation operator in the distortion constraint of Definition 1 is natural to readers familiar with rate-distortion theory. From a computer science perspective, it follows the philosophy of approximate computing [11]. Nevertheless, hard constraints on the accuracy of computation can be addressed via distortion metrics based on the infinity norm, which enforces a maximum tolerable distortion.  
The computational cost operator may also include an expectation. Whether this is appropriate or not depends on the goal of the hardware design. If the purpose is minimum chip area, one usually must be able to deal with the worst case and an expectation can be inappropriate. Power consumption, on the other hand, overwhelmingly correlates with average computational cost.  
The above definitions shall not be confused with related, but different definitions in the literature of approximation theory [12]. There, the purpose is rather to allow for proving theoretical achievability bounds than evaluating algorithms. The approach to distortion is similar. Complexity, however, is measured as the growth rate of the number of bits required to achieve a given upper bound on distortion. This is quite different from the computational cost in Definition 2.