## 3 Improve L1 Optimization to Correct 100% of Corrupted Propagated Errors in Network Coding
### Compressed Header Overhead  
The header overhead in network coding is a very important issue in Algorithm 1 because this algorithm mainly copes with the environment of random network coding. The header overhead problem is very relevant to our scheme. There are two main methods to decrease the header overhead: the block transmission and the compressed header overhead. [PERSON] gives the format about random network coding. The procedure of network coding in Figure 3 can be expressed as the following equation. \[\left[ \begin{array}{ccc}Y_{1}^{1}&\ldots&Y_{1}^{b}\\ Y_{2}^{1}&\ldots&Y_{2}^{b}\\ \ldots&\ldots&\ldots\\ Y_{K}^{1}&\ldots&Y_{K}^{b}\end{array} \right]=T.\left[ \begin{array}{ccc}X_{1}^ {1}&\ldots&X_{1}^{b}\\ X_{2}^{1}&\ldots&X_{2}^{b}\\ \ldots&\ldots&\ldots\\ X_{n}^{1}&\ldots&X_{n}^{b}\end{array} \right]=\left[ \begin{array}{ccc}g_{1,1 }&g_{1,2}&\ldots&g_{1,n}\\ g_{2,1}&g_{2,2}&\ldots&g_{2,n}\\ \ldots&\ldots&\ldots\\ g_{K,1}&g_{K,2}&\ldots&g_{K,n}\end{array} \right]\left[ \begin{array}{ccc}X_{1}^ {1}&\ldots&X_{1}^{b}\\ X_{2}^{1}&\ldots&X_{2}^{b}\\ \ldots&\ldots&\ldots\\ \ldots&\ldots&\ldots\\ X_{n}^{1}&\ldots&X_{n}^{b}\end{array} \right] \tag{12}\]  
In this equation, the transfer matrix from the source to the sink node is \(\left[ \begin{array}{ccc}g_{1,1}&g_{1,2}&\ldots&g_{1,n}\\ g_{2,1}&g_{2,2}&\ldots&g_{2,n}\\ \ldots&\ldots&\ldots\\ g_{K,1}&g_{K,2}&\ldots&g_{K,n}\end{array} \right]\) which is denoted as \(T\). The decoding can be performed successfully if and only if \(K\geq n\) and \(T\) is invertible. In Figure 3, the size of generation is \(n\), and the size of block is \(b\). The definition of generation and block are referred in [30; 31]. The cost of network coding scheme is the overhead of transmitting extra symbols in each packet. If we increase the size of block, which is the number of symbols about messages in a packet, the normalized overhead can be reduced. However, in Algorithm 1, we cannot increase the size of block without limit because the \(b=\frac{m+n}{\mathbb{C}}=\frac{m+n}{n}\). If we increase the size of \(b\), we have to increase \(\frac{m}{n}\). As illustrated in above paragraph, we know that the optimal value of \(\frac{m}{n}\) is \(\mathbf{4}\). If \(\frac{m}{n}\) is not equal to \(4\), the effectiveness of L1 optimization will reduce. Thus, though the method of block transmission has certain effectiveness, we cannot take advantage of this method unlimitedly. Another method is to compress header overhead, about which there are many works [32; 33]. Among them, the latest important work about compress header overhead is [33] which is very interesting and useful. [PERSON] and so on use compressed sparse row (CSR) technique to reduce the header overhead [33]. Find the Optimal Number and Optimal Positions of Relay Nodes in Network Coding with Social Networks  
In Algorithm 1, we always assume the matrix \(Y\) in \(Y=\hat{T}\cdot y+T_{Z\to Y}\cdot(Z-Ly)\) is full rank. However, in the actual environment, the matrix \(Y\) may not always be full rank which is the famous \"all-or-nothing\" problem in random network coding [26]. If \(Y\) is not full rank, the effectiveness of Algorithm 1 will be undermined greatly. Certainly, we can keep receiving fresh packets from the network until \(Y\) is full rank. Thus, if we consume more time and energy to receive more packets until \(Y\) is full rank, the procedure of Algorithm 1 can be done unaffectedly. However, it will consume too many resources such as the energy and the time to receive more packets until \(Y\) is full rank. Therefore, we must additionally find a method to hedge the consumed resource resulting from receiving more packets until \(Y\) is full rank. For a certain network, when all the relay nodes perform network coding, assume the number of packets which are received ceaselessly until \(Y\) is full rank which is \(\Upsilon\). A possible method is to choose only a part of relay nodes other than all of them to perform network coding  
Figure 3: The packet format of practical network coding.