m-BRe: New Variants for the Backward Replacement Approach to Enhance the Compression Capabilities of the Forward Greedy Pursuit

This paper introduces two variants of the backward replacement approach, T-BRe and H-BRe, aimed at enhancing the compression capabilities of forward greedy pursuit algorithms. The effectiveness of these methods is evaluated using three greedy pursuit algorithms (OMP, OOMP, and FBP) through simulations conducted on image and speech datasets with a mathematically generated dictionary. Additionally, a mathematical analysis of the H-BRe algorithm is provided to validate its effectiveness and address inherent limitations. Both analysis and simulations confirm that the H-BRe algorithm significantly improves the compression capabilities of forward greedy pursuit algorithms. The degree of enhancement varies depending on factors such as the forward modeling technique, stopping criterion, and the stochastic nature of the backward replacements. The high-performance (H) variants demonstrate superior performance across various modeling approaches, as evidenced by metrics such as PESQ and SSIM values, while the B and T variants also exhibit efficiency in specific scenarios. Despite these promising results, our methods encounter limitations such as time complexity, local error minimization, dependence on atom types, and the assumption of linear distribution. Future research directions include optimizing time complexity, balancing compression-quality trade-offs, globally minimizing replacement errors, exploring diverse atom types, and refining mathematical assumptions to further elucidate H-BRe’s performance characteristics.

SECTION I. Introduction

Data compression, a fundamental aspect of information theory and computer science, holds a crucial position in facilitating the effective storage, transmission, and manipulation of digital data. Through the reduction of data file or stream sizes, compression methods strive to preserve storage capacity and enhance bandwidth efficiency while ensuring the integrity of essential information remains intact. Claude Shannon’s groundbreaking work in [1] established the foundational concepts for comprehending data compression principles within the realm of information theory. Subsequently, numerous studies have propelled the evolution of compression algorithms and strategies, encompassing both lossless and lossy compression methodologies.

Sparse coding stands as a potent method within data compression, striving to depict data through a concise assortment of non-zero coefficients. Its prominence spans diverse fields like signal processing, computer vision, and machine learning, owing to its aptitude for encapsulating the inherent structure and redundancy within data. Leveraging the sparsity inherent in signals, sparse coding provides an effective avenue for data representation, facilitating streamlined storage and transmission of information.

Sparse approximation challenges aim for a reliable estimation of an input signal $\boldsymbol {X}\in \mathbb {R}^{M}$ by expressing it as a linear combination of fundamental signals known as “atoms” derived from a dictionary $\boldsymbol {\Phi }\in \mathbb {R}^{M\times N}$ . However, these challenges specify that the approximation should involve only a limited number of these elementary signals.

Based on recent studies, researchers have found that the sparse representation problem can be addressed through forward, backward, or simultaneous application of both techniques. There are several algorithms that exist for the forward solution, known as Forward Greedy (FG) algorithms. These include Matching Pursuit (MP) [2], Orthogonal MP (OMP) [3], Improved OMP [4], [5], Distributed Compressed Sensing—Subspace OMP (DCS-SOMP) [6], Optimized OMP (OOMP) [7], Stagewise OMP (StOMP) [8], Multi-Stage OMP [9], Compressive Sampling MP (CoSaMP) [10], SAMP [11], ROMP [12], gOMP [13], $\text {OMP}_{\alpha }$ [14], CSMPSP [15], among others. On the other side, there are several backward solutions for solving the sparse coding problem such as Backward OOMP (BOOMP) [16], Forward-Backward greedy algorithm (FoBa) [17], Forward-Backward GP (FBGP) [18], Backward Greedy Algorithm (BGA) [19] and FBP [20] are based on the fact that the selected atoms by any FG algorithm can be reduced by eliminating some of them and the elimination error can be compensated if and only if the atoms are not orthogonal to each other. FoBa, FBGP and FBP have built-in OMP-based FG algorithm such that after each forward iteration there is also a backward iteration. Unlike them, both BOOMP and BGA are pure backward processing that works after finishing the forward modelling.

When focusing on bit-oriented compression, sparse modeling encounters several challenges. Firstly, transmitting only the atoms’ coefficients is insufficient; the locations of these coefficients in the sparse vector also need to be sent, requiring more bits per coefficient. Additionally, as discussed in our earlier work [21], highly correlated atoms can hinder compression performance, particularly due to the elimination process inherent in backward solutions. Therefore, we concentrated on developing an effective and resilient backward strategy for forward sparse greedy algorithms, specifically for speech compression. Existing backward methods typically involve progressively setting more coefficients to zero while adjusting the remaining non-zero coefficients. Our latest approach, termed the Binary-Backward Replacement (B-BRe) algorithm, aims to replace the k-sparse coefficients vector with a k-sparse symmetric matrix, in which two coefficients are augmented and replaced with one coefficient, enabling us to remove some coefficients while maintaining effectiveness. The main outcome of [21] shows that this replacement technique significantly outperforms existing backward elimination algorithms, enhancing the compression capabilities of the FG algorithms.

This study introduces two novel variations of the B-BRe algorithm: Ternary-Backward Replacement (T-BRe) and Hybrid-BRe (H-BRe). Unlike the original B-BRe, T-BRe enhances the process by simultaneously augmenting three coefficients. This modification aims to increase the number of coefficients that are eliminated in a single step. On the other hand, H-BRe incorporates a dual approach where both B-BRe and T-BRe algorithms operate in parallel. The selection between the two is determined based on the achieved level of bit-level compression, ensuring optimal performance.

The structure of this article is organized as follows: In Section II, we provide a comprehensive overview of the B-BRe algorithm, detailing its foundational concepts and operational mechanics. Following this, Sections III and IV introduce the proposed methodologies, T-BRe and H-BRe, respectively. These sections delve into the specific enhancements and parallel processing techniques that distinguish these algorithms from the original B-BRe. Section V is dedicated to presenting the simulation study, encompassing all experimental results and in-depth discussions of the findings. The limitations and practical applicability of the proposed algorithms are thoroughly examined in Section VI. Finally, the conclusions drawn from this study are provided in Section VII, summarizing the key outcomes and implications of our research. Additionally, the proofs of three critical theorems supporting our methodologies are detailed in Appendices A, B, and C, offering a rigorous mathematical foundation for the proposed algorithms. Most of the notations and acronyms used in this study are listed in Table 1.

TABLE 1 Notations and Acronyms Used in This Paper

SECTION II. The Binary-Backward Replacement Approach

A. Forward Greedy and Backward Eliminations

Starting from the FG algorithms, their primary objective is to achieve a satisfactory approximation for $\boldsymbol {X} \in \mathbb {R}^{M}$ using only k atoms from the dictionary $\boldsymbol {\Phi }$ , where $k \lt M$ , by minimizing the following objective function:

$$\begin{equation*} \min \|\boldsymbol {X} - \boldsymbol {\Phi }\boldsymbol {w}\|_{2}^{2} \quad \text {s.t.} \quad \|\boldsymbol {w}\|_{0} = k \tag {1}\end{equation*}$$

The solution to this objective function, denoted as $\boldsymbol {w}_{k}$ , is a vector of k non-zero coefficients, and the resulting approximation is given by $\boldsymbol {\Phi }\boldsymbol {w}_{k}$ . If a backward phase is employed, the vector $\boldsymbol {w}_{k}$ is manipulated to enhance sparsity by minimizing the following objective function:

$$\begin{equation*} \min \|\boldsymbol {w}_{k}\|_{0} \quad \text {s.t.} \quad \|\boldsymbol {X} - \boldsymbol {\Phi }\boldsymbol {w}_{k}\|_{2}^{2} \leq \alpha \|\overrightarrow {\boldsymbol {e}}_{k-1}\|_{2}^{2} \tag {2}\end{equation*}$$

Here, $\alpha$ is a real number less than or equal to 1, ensuring that the backward processing does not nullify the overall gain achieved in the previous forward step. Additionally, $\overrightarrow {\boldsymbol {e}}_{k-1}$ represents the residual vector at the $(k-1)$ forward step. Existing backward processing techniques, such as BOOMP [16], FoBa [17], FBP [18], and BGA [19], operate on the premise that the atoms selected by any FG algorithm can be reduced by eliminating some of them. However, these methods fail when the atoms are orthogonal or quasi-orthogonal to each other. Furthermore, their efficiency inversely correlates with the recovery performance of the FG algorithm, because the FG algorithm aims to select the smallest independent set of atoms during the forward iterations, making it difficult to compensate for elimination errors through these atoms.

B. Effect of Backward Eliminations on Data Compression

As previously demonstrated, sparse modeling inherently encourages direct utilization in data compression due to its use of minimal coefficients and indices to represent data. If we denote $B_{c}$ and $B_{i}$ as the number of bits allocated for the quantized coefficient and its index respectively, encoding the vector $\boldsymbol {w}_{k}$ necessitates $k(B_{c} + B_{i})$ bits. Backward elimination techniques aim to discover a subset of $k'$ coefficients such that $k' \lt k$ and $\|\boldsymbol {X} - \boldsymbol {\Phi }\boldsymbol {w}_{k}\|_{2}^{2} \approx \|\boldsymbol {X} - \boldsymbol {\Phi }\boldsymbol {w}_{k'}\|_{2}^{2}$ . Consequently, the achieved compression ratio can be expressed as $1-\frac {k'}{k}$ . As previously mentioned, elimination proves advantageous when the atoms are minimally correlated. Conversely, if they exhibit high correlation, resulting in $\frac {k'}{k}\approx 1$ , negligible compression is realized. To overcome the dependency of eliminations and the atoms’ correlations, a backward replacement solution has been proposed and analyzed in detail in [21].

C. Replacements Instead of Eliminations

In contrast to backward eliminations, [21] introduced a backward replacement method called Binary-Backward Replacement (B-BRe). In B-BRe, if two coefficients in $\boldsymbol {w}_{k}$ are set to be equal, only one coefficient needs to be encoded, while the indices of both coefficients remain unchanged. This process is known as partial elimination, where a coefficient is removed but its index is retained. If this process is applied to $r_{b}$ pairs of coefficients, the coefficient vector $\boldsymbol {w}_{k}$ is updated to $\boldsymbol {w}^{r_{b}}_{k}$ , and the total number of bits required to encode $\boldsymbol {w}^{r_{b}}_{k}$ becomes $(k-r_{b})B_{c} + kB_{i}$ instead of $k(B_{i} + B_{c})$ .

The detailed function of B-BRe is illustrated in Figure 1. As shown, the overall methodology is conducted through six sequential steps. In the first step, the indices of the k non-zero coefficients of $\boldsymbol {w}_{k}$ are listed in a set $\Gamma = \{\Gamma _{1}, \Gamma _{2}, \ldots, \Gamma _{k}\}$ , and the range of $\Gamma$ is a subset of $\{1, 2, \ldots, N\}$ .

FIGURE 1.

Workflow diagram of B-BRe algorithm.

Identifying all possible pairs of indices $\Gamma ^{x,y} = \{\Gamma _{x}, \Gamma _{y}\}$ , such that $1 \le x \le k-1$ and $x \lt y \le k$ , is conducted in the second step. Then, in the third step, all possible pairs of coefficients are determined as vectors $\boldsymbol {W}_{x,y} = \left [{{ w_{\Gamma _{x}} \ \ w_{\Gamma _{y}} }}\right]$ along with the corresponding matrix of atoms $\boldsymbol {\Phi }_{x,y} = \left [{{ \boldsymbol {\varphi }_{\Gamma _{x}} \ \ \boldsymbol {\varphi }_{\Gamma _{y}} }}\right]$ . By the end of this step, there are $k(k-1)$ possible pairs of coefficients.

In the fourth step, each pair of coefficients $\boldsymbol {W}_{x,y}$ is replaced with one coefficient $W'_{x,y} = \frac {w_{\Gamma _{x}} + w_{\Gamma _{y}}}{2}$ such that the resulting error $\|\boldsymbol {\Phi }_{x,y}\boldsymbol {W}^{T}_{x,y} - W'_{x,y} (\boldsymbol {\varphi }_{\Gamma _{x}}+\boldsymbol {\varphi }_{\Gamma _{y}})\|^{2}_{2}$ is minimized to its minimum value $(1-\mu _{xy}) (w_{\Gamma _{x}}-w_{\Gamma _{y}})^{2}/2$ , where $\mu _{xy} = \boldsymbol {\varphi }_{\Gamma _{x}}^{T}\boldsymbol {\varphi }_{\Gamma _{y}}$ .

In the fifth step, all replacement errors obtained from the $k(k-1)$ replacements are stored in the distortion matrix $\Upsilon$ . Then, at the last step, $r_{b}$ replacements only are selected from the overall replacements $k(k-1)$ . These $r_{b}$ replacements have the least error values in the distortion matrix $\Upsilon$ . After determining the $r_{b}$ replacements, the coefficients vector $\boldsymbol {w}_{k}$ is updated to $\boldsymbol {w}_{k}^{r_{b}}$ and encoded by $kB_{i} + (k-r_{b})B_{c}$ , and the approximation error becomes $\|\boldsymbol {X}-\boldsymbol {\Phi }\boldsymbol {w}_{k}^{r_{b}}\|$ .

For error-driven forward and backward representations, let’s consider $\epsilon$ as the modeling error after selecting k atoms, and assume that the replacement errors are negligible. In this case, the compression ratio can be expressed as $1-\frac {(k-r_{b})B_{c} + k B_{i}}{k (B_{c} + B_{i})}$ . This is because a single replacement results in coefficient elimination but not index elimination.

D. The Order of Replacements

From a data compression perspective, B-BRe demonstrated that the replacement process is pivotal in reducing the bits assigned to coefficients. In this study, we introduce a novel variant of backward replacement, where three coefficients are grouped and replaced instead of two.

SECTION III. The Ternary-Backward Replacement Approach (T-BRe)

Expanding on B-BRe, this study proposes an enhanced backward replacement strategy called Ternary-Backward Replacement (T-BRe), which applies a higher replacement order to the coefficients vector $\boldsymbol {w}_{k}$ . The term “Tri” indicates the grouping of coefficients into ternary sets. In this method, each set of three coefficients is replaced with another coefficient that minimizes the replacement error. Additionally, the distortion matrix is a symmetric 3D matrix that records all potential replacement errors for all possible replacements. The workflow of T-BRe is illustrated in Figure 2.

FIGURE 2.

Workflow diagram of T-BRe algorithm.

A. Replacement Coefficient and Replacement Error

As previously mentioned, the primary concept underlying this type of index grouping involves replacing a set of three coefficients with another coefficient that minimizes the replacement error. Consider an arbitrary ternary subset of indices $\Gamma ^{x,y,z}=\{\Gamma _{x},\Gamma _{y},\Gamma _{z}\}$ , with the corresponding coefficients vector $\boldsymbol {W}_{x,y,z}=\left [{{ w_{\Gamma _{x}}, w_{\Gamma _{y}}, w_{\Gamma _{z}} }}\right]$ , and the corresponding sub-dictionary $\boldsymbol {\Phi }_{x,y,z}=\left [{{ \boldsymbol {\varphi }_{\Gamma _{x}}, \boldsymbol {\varphi }_{\Gamma _{y}}, \boldsymbol {\varphi }_{\Gamma _{z}} }}\right]$ .

When the three coefficients in $\boldsymbol {W}_{x,y,z}$ are replaced with a new coefficient $W'_{x,y,z}$ , the replacement error vector $\boldsymbol {e}$ is computed as follows:

$$\begin{align*} \boldsymbol {e} & = (w_{\Gamma _{x}}\boldsymbol {\varphi }_{\Gamma _{x}}+w_{\Gamma _{y}}\boldsymbol {\varphi }_{\Gamma _{y}}+w_{\Gamma _{z}}\boldsymbol {\varphi }_{\Gamma _{z}}) \\ & \quad - \ \ W'_{x,y,z} (\boldsymbol {\varphi }_{\Gamma _{x}}+\boldsymbol {\varphi }_{\Gamma _{y}}+\boldsymbol {\varphi }_{\Gamma _{z}}) \tag {3}\\ & = \boldsymbol {\Phi }_{x,y,z} \boldsymbol {W}^{T}_{x,y,z} - \boldsymbol {\Phi }_{x,y,z} \boldsymbol {I}^{T} W'_{x,y,z} \tag {4}\end{align*}$$ and the corresponding mean squared error is: $$\begin{equation*} \lVert \boldsymbol {e}\rVert ^{2}_{2} = \lVert \boldsymbol {\Phi }_{x,y,z} \boldsymbol {W}^{T}_{x,y,z} - \boldsymbol {\Phi }_{x,y,z} \boldsymbol {I}^{T} W'_{x,y,z}\rVert ^{2}_{2} \tag {5}\end{equation*}$$ where $\boldsymbol {I} = [1\ \ 1\ \ 1]$ is the ternary vector of ones.

Theorem 1:

The value of $W'_{x,y,z}$ that minimizes (5) could be calculated by:

$$\begin{equation*} W'_{x,y,z} = \frac {\boldsymbol {W}_{x,y,z}\boldsymbol {\Phi }^{T}_{x,y,z}\boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T}}{\boldsymbol {I}\boldsymbol {\Phi }_{x,y,z}^{T} \boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T}}, \tag {6}\end{equation*}$$ and the corresponding mean squared error is, (7), as shown at the bottom of the next page, $$\begin{equation*} {\lVert \boldsymbol {e}\rVert ^{2}_{2} = \boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }- \boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T} \frac {\boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}} - \frac {\boldsymbol {I} \boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}I \boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }+ \frac {I \boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}I \boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T} \frac {\boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}} } \tag {7}\end{equation*}$$ where the subscript $\gamma$ denotes $x,y,z$ .

Proof:

The proof of this theorem is provided in Appendix A.

Corollary 2 ($W'_{x,y,z}$ in the case of Ortho-normal bases):

For ortho-normal atoms, we have $\boldsymbol {\Phi }^{T}_{x,y,z}\boldsymbol {\Phi }_{x,y,z}= \mathbb {I}$ , where $\mathbb {I}$ is the identity matrix. Substituting into (6), we obtain $W'_{x,y,z} = \frac {\boldsymbol {W}_{x,y,z}\mathbb {I}\boldsymbol {I}^{T}}{\boldsymbol {I}\mathbb {I} \boldsymbol {I}^{T}}$ , which simplifies to $\frac {\boldsymbol {W}_{x,y,z}\boldsymbol {I}^{T}}{3}$ .

The minimum replacement error is then:

$$\begin{equation*} \lVert \boldsymbol {e}\rVert ^{2}_{2} = \boldsymbol {W}_{x,y,z} \boldsymbol {W}^{T}_{x,y,z} - \frac {1}{3}(\boldsymbol {W}_{x,y,z} \boldsymbol {I}^{T})^{2} \tag {8}\end{equation*}$$

B. Cubic Distortion Matrix and the Selection Criterion

In the T-BRe algorithm, a primary task involves constructing the cubic distortion matrix ${\Upsilon }\in \mathbb {R}^{k\times k\times k}$ . Specific positions within this matrix are populated with mean squared error values defined as follows:

$$\begin{equation*} \Upsilon _{x,y,z}=\lVert \boldsymbol {\Phi }_{x,y,z} \boldsymbol {W}^{T}_{x,y,z} - \boldsymbol {\Phi }_{x,y,z} \boldsymbol {I}^{T} W'_{x,y,z}\rVert ^{2}_{2} \tag {9}\end{equation*}$$ where $1 \le x \le k-2$ , $x \lt y \le k-1$ , and $y \lt z \le k$ . Note that all other positions in the cubic matrix remain empty.

The second main task in the T-BRe algorithm is to select the coefficients $(w_{\Gamma _{x}}, w_{\Gamma _{y}}, w_{\Gamma _{z}})$ where their replacement error is minimized in $\Upsilon$ . At backward iteration i,

$$\begin{equation*} \Gamma ^{x,y,z} = \arg \inf \limits _{\forall x,y,z}\{\Upsilon _{x,y,z}\} \tag {10}\end{equation*}$$ Thus, the content of the selected position is updated to be empty, i.e., $\Upsilon _{x,y,z} = \emptyset$ , to exclude it from subsequent searches. Next, the coefficients vector $\boldsymbol {w}^{i}_{k}$ is updated by assigning the new value $W'_{x,y,z}$ to the coefficients located at $\Gamma ^{x,y,z} = \{\Gamma _{x}, \Gamma _{y}, \Gamma _{z}\}$ . The overall representation error is then updated as follows: $$\begin{equation*} \lVert \boldsymbol {X}-\hat {\boldsymbol {X}} \rVert ^{2}_{2} = \lVert \boldsymbol {X}-\boldsymbol {\Phi } \boldsymbol {w}^{i}_{k} \rVert ^{2}_{2} \tag {11}\end{equation*}$$

The backward iteration proceeds until a predefined normalized error threshold $\epsilon$ is attained, defined as $\epsilon = \frac {\lVert \boldsymbol {X}-\boldsymbol {\Phi } \boldsymbol {w}^{i}_{k} \rVert ^{2}_{2}}{\lVert \boldsymbol {X}-\boldsymbol {\Phi } \boldsymbol {w}^{0}_{k} \rVert ^{2}_{2}}$ , where $\boldsymbol {w}^{0}_{k}$ represents the coefficients vector obtained from the forward modeling process.

C. T-BRe’s Complexity Analysis

To analyze the complexity of the T-BRE algorithm in details, we have provided the pseudo code in Figure 3.

FIGURE 3.

T-BRe’s pseudo code.

The time complexity of the T-BRe algorithm can be analyzed as follows:

1. Initialization: Constant time operations.$O(1)$

2. For Loop (Lines 5-11):

   • This loop iterates over combinations of indices x, y, and z, where x ranges from 1 to $k-2$ , y ranges from x to $k-1$ , and z ranges from y to k. The number of iterations is roughly $\frac {k^{3}}{6}$ .

   • Inside the loop, operations like obtaining subsets of indices ($\Gamma ^{x,y,z}$ ), creating ternary vectors and matrices, and performing matrix operations are performed. The time complexity of these operations depends on the size of the data structures and the complexity of the matrix operations.

   • Time complexity: $O(k^{3})$ .

3. Loop (Lines 12-25):

   • This loop iterates until a termination condition is met. The number of iterations depends on the convergence of the algorithm, which may vary.

   • Inside the loop, operations involve finding the minimum value stored in $\Upsilon$ , updating coefficients, calculating error ratios, and checking termination conditions. The time complexity of these operations depends on the convergence behavior of the algorithm.

   • Time complexity: It is hard to determine a precise worst-case time complexity for this loop because it depends on the convergence rate behavior.

4. For Loop (Lines 26-29):

   • The loop iterates over the remaining $k-2r_{t}$ indices that are not included in $\Gamma ^{t}$ .

   • Within the loop, operations include obtaining subsets of indices, generating coefficient bitstreams, and updating counters. The time complexity is influenced by the size of the data structures.

   • Time complexity: $O(k-2r_{t})$ .

5. Return: Constant time operations.$O(1)$

Overall, the time complexity of the T-BRe algorithm is dominated by the operations performed inside the nested loops, particularly the first loop iterating over combinations of indices. Therefore, the overall time complexity of the algorithm can be approximated as $O(k^{3})$ , where k is the size of the input data structures.

D. Bitstream and Compression Analysis

Figure 4 illustrates the proposed bitstream structure for the T-BRe algorithm. It features a two-layered design: Layer 1 contains the bitstream for the individual coefficients and indices, while Layer 2 is dedicated to the replacement coefficients and their respective indices. In the next section (Theorem 3), we will explore the conditions under which T-BRe outperforms B-BRe in terms of bit compression efficiency.

FIGURE 4.

Proposed bitstream structure for T-BRe. Note: Each ternary set of indices requires $3B_{i}$ bits, and $r_{t}$ ternary sets of indices require $3r_{t} B_{i}$ bits.

Theorem 3:

(Minimum and Maximum Replacements for T-BRe): In the view of data compression, and comparing to B-BRe, the minimum replacements required by T-BRe to get compression more than B-BRe is $r_{t} = \frac {r_{b}}{2}$ , and the maximum available replacements is $\frac {k}{3}$ , where $r_{t}$ is the number of replacements in T-BRe, $r_{b}$ is the number of replacements in B-BRe, k is the number of non zero coefficients.

Proof:

Assume $B_{c}$ and $B_{i}$ are the number of bits required to encode one coefficient and its index in the sparse vector respectively. Then the total number of bits required to encode the k coefficients in B-BRe algorithm is called the Compressed Data Size $\text {CDS}_{B}$ :

$$\begin{equation*} \text {CDS}_{B} = (k-r_{b})B_{c} + kB_{i}, \tag {12}\end{equation*}$$ and the total number of bits required to encode the k coefficients in T-BRe algorithm is $\text {CDS}_{T}$ : $$\begin{equation*} \text {CDS}_{T} = (k-2r_{t})B_{c} + kB_{i} \tag {13}\end{equation*}$$ From (12) and (13), it becomes clear that: $$\begin{align*} \text {CDS}_{T} \lt & \ \text {CDS}_{B} \\ (k-2r_{t})B_{c} + kB_{i} \lt & \ (k-r_{b})B_{c} + kB_{i} \\ r_{t} \gt & \ \frac {r_{b}}{2} \tag {14}\end{align*}$$ Since the sparse vector includes $k$ non-zero coefficients, the maximum ternary selections are $\frac {k}{3}$ . So, the range of $r_{t}$ to achieve more compression by T-BRe than B-BRe is: $$\begin{equation*} \frac {r_{b}}{2}\ \lt \ r_{t}\ \le \ \frac {k}{3} \tag {15}\end{equation*}$$

SECTION IV. The Hybrid-Backward Replacement Approach (H-BRe)

In addition to T-BRe, this study introduces a new variation of the backward replacement approach called the hybrid algorithm H-BRe, which combines the B-BRe and T-BRe methods during backward processing. As shown in the pseudo code for H-BRe in Figure 5, both B-BRe and T-BRe are applied to a vector $\boldsymbol {X}$ to generate corresponding bitstreams. The bitstream that minimizes the total number of bits is then selected. According to the findings in (14), T-BRe outperforms B-BRe when $r_{t} \gt \frac {r_{b}}{2}$ . Thus, the choice between the two algorithms is based on comparing $r_{b}$ and $r_{t}$ .

FIGURE 5.

H-BRe’s pseudo code.

The subsequent question addresses the level of compression achievable with the hybrid technique. To answer this, the randomness of both $r_{b}$ and $r_{t}$ must be analyzed to calculate the probability $\rho = Pr \left [{{ r_{t} \gt \frac {r_{b}}{2}}}\right]$ , which is critical for expected improvements. Theorem 4 derives $\rho$ under specific conditions.

Theorem 4:

If both $r_{b}$ and $r_{t}$ are independent random variables with linear distributions, their respective distribution functions can be expressed as $f(r_{b}) = a_{b} r_{b} + b_{b}$ and $f(r_{t}) = a_{t} r_{t} + b_{t}$ . In this case, the probability $\rho = Pr \left [{{ r_{t} \gt \frac {r_{b}}{2} }}\right]$ can be calculated as follows:

$$\begin{equation*} \rho = G_{1}^{(4)}(k) a_{b} a_{t} + G_{2}^{(2)}(k) a_{b} + G_{3}^{(2)}(k) a_{t} + G_{4}^{(0)}(k) \tag {16}\end{equation*}$$ where $G^{(4)}(k)$ , $G^{(2)}(k)$ and $G^{(0)}(k)$ are fourth-degree, second-degree and zero-degree rational functions respectively.

Proof:

The proof of this theorem is provided in Appendix B

Corollary 5 ($\rho$ at the bounds of$a_{b}$ and$a_{t}$ ):

From (41), we can conclude that, the bounds of $a_{b}$ are $a_{b}^{+} = \frac {8}{k(k+2)}$ , $a_{b}^{-} = \frac {-8}{k(k+2)}$ , and the bounds of $a_{t}$ are $a_{t}^{+} = \frac {18}{k(k+3)}$ , $a_{b}^{-} = \frac {-18}{k(k+3)}$ . By substituting in (48), we have four possible values for $\rho$ .

$$\begin{align*} \rho (a_{b}^{+}, a_{t}^{+}) & = \frac {26k^{3} + 85k^{2} + 18k - 96}{32 k(k+2)(k+3)} \tag {17}\\ \rho (a_{b}^{+}, a_{t}^{-}) & = \frac {6k^{3} - 53k^{2} - 82k + 96}{32 k(k+2)(k+3)} \tag {18}\\ \rho (a_{b}^{-}, a_{t}^{+}) & = \frac {32k^{3} + 145k^{2} + 210k + 96}{32 k(k+2)(k+3)} \tag {19}\\ \rho (a_{b}^{-}, a_{t}^{-}) & = \frac {16k^{3} - 17k^{2} - 146k - 96}{32 k(k+2)(k+3)} \tag {20}\end{align*}$$

From the previous values of $\rho$ , we can find that,

$$\begin{align*} \lim _{k \to \infty } \rho (a_{b}^{+}, a_{t}^{+}) & \approx \frac {13}{16} \tag {21}\\ \lim _{k \to \infty } \rho (a_{b}^{+}, a_{t}^{-}) & \approx \frac {3}{16} \tag {22}\\ \lim _{k \to \infty } \rho (a_{b}^{-}, a_{t}^{+}) & \approx 1 \tag {23}\\ \lim _{k \to \infty } \rho (a_{b}^{-}, a_{t}^{-}) & \approx \frac {1}{2}. \tag {24}\end{align*}$$

Corollary 6 (Uniformly Distributed$r_{b}$ and$r_{t}$ ):

For the uniformly distributed $r_{b}$ , and $r_{t}$ , we have $a_{b} = a_{t} = 0$ , then by substituting in (48), the value of $\rho$ can be simplified to:

$$\begin{equation*} \rho = \frac {5k}{8k + 24} \tag {25}\end{equation*}$$

Corollary 7 ($\rho$ at Large k):

For the linearly distributed $r_{b}$ and $r_{t}$ , the value of $\rho$ tends to be $\frac {5}{8}$ at the large values of $k$ , because $a_{b} a_{t} \propto \frac {4}{k^{4}}$ , $a_{b} \propto \frac {2}{k^{2}}$ and $a_{t} \propto \frac {2}{k^{2}}$ , then by taking the limit $\lim _{k \to \infty } p$ we get:

$$\begin{equation*} \lim _{k \to \infty } \rho (k) \approx \frac {5}{8} \tag {26}\end{equation*}$$

Theorem 8 (The Expected Compression Percentage of H-BRe):

If we assumed that $\rho$ is the probability that $r_{t}\gt \frac {r_{b}}{2}$ , and $1-\rho$ is the probability that $r_{t} \le \frac {r_{b}}{2}$ , and both $r_{b}$ and $r_{t}$ are independent and linearly distributed random variables such that their distribution functions are $a_{b} r_{b} + b_{b}$ and $a_{t} r_{t} + b_{t}$ respectively, then the expected compression percentage of H-BRe is:

$$\begin{equation*} {\mathcal {CP}}_{H} = \frac {\left [{{ F_{1} k^{2} + F_{2} k - (F_{3} - 1) }}\right ] B_{c}}{\left ({{ B_{i} + B_{c}}}\right) }\times 100\% \tag {27}\end{equation*}$$ where, $$\begin{align*} F_{1} & = \frac {(1-\rho)a_{b}}{96}+\frac {\rho a_{t}}{162} \tag {28}\\ F_{2} & = \frac {(1-\rho)a_{b}}{16}+\frac {\rho a_{t}}{18} \tag {29}\\ F_{3} & = \frac {(1-\rho)(9-a_{b})}{12}+\frac {\rho (6-a_{t})}{9} \tag {30}\end{align*}$$

Proof:

The proof of this theorem is provided in Appendix C

Corollary 9:

For the uniformly distributed $r_{b}$ and $r_{t}$ , we have $a_{b} = a_{t} = 0$ then ${\mathcal {CP}}_{H}$ can be simplified to:

$$\begin{equation*} {\mathcal {CP}}_{H} = \frac {\left ({{\frac {\rho }{12}+\frac {1}{4}}}\right)B_{c}}{B_{i} + B_{c}} \times 100\% \tag {31}\end{equation*}$$ From (25), we can find that: $$\begin{equation*} {\mathcal {CP}}_{H} = \frac {\left ({{ \frac {\frac {5}{12} k}{8k+24}+\frac {1}{4}}}\right) B_{c}}{B_{i} + B_{c}} \times 100\% \tag {32}\end{equation*}$$ Also, we find that: $$\begin{equation*} \lim _{k \to \infty }{\mathcal {CP}}_{H} = \frac {\frac {29}{96} B_{c}}{B_{i} + B_{c}} \times 100\% \tag {33}\end{equation*}$$

SECTION V. Simulation Results and Analysis

A. Simulation Environment

To assess the effectiveness of the proposed methods in enhancing B-BRe compression performance [21], a diverse range of datasets containing speech and image data was utilized. All algorithms were implemented in Matlab 2023b and executed on a server featuring an Intel Xeon(R) Gold 6330 CPU running at 2.00GHz with 23 GB of RAM, operating on Windows 10, provided by the Egyptian Electronics Research Institute’s datacenter.

The datasets included the widely-used speech database TIMIT [22], along with various image datasets [23], [24], [25]. In light of the sparse modeling phase in our proposed methods, we utilized three greedy pursuit algorithms—OMP [3], OOMP [7], and FBP [20]—as initial stage for the backward processing techniques B-BRe, T-BRe, and H-BRe. The notations OMP-B, OMP-T, and OMP-H represent combinations like (OMP + B-BRe), (OMP + T-BRe), and (OMP + H-BRe), respectively. Similar naming conventions were applied to OOMP and FBP.

B. Encoder Configuration

Our proposed encoder closely resembles the one depicted in Figure 6. As previously mentioned, in our conducted experiments, the initial stage of the encoding process involves employing the forward greedy pursuit. This stage yields the sparse vector $\boldsymbol {w}_{k}$ , which is then processed in reverse using either B-BRe, T-BRe, or H-BRe to determine both individual and combined indices along with their corresponding coefficients. Subsequently, the coefficients undergo quantization before proceeding to the final phase, during which both indices and quantized coefficients are converted into bitstreams.

FIGURE 6.

The suggested BRe-based encoder.

For the TIMIT dataset, we utilized 200 speech signals, each undergoing downsampling to 8 kHz (8000 samples per second) and quantization to 2 bytes (16 bits) per sample. Prior to the forward transformation, the speech signals were segmented into segments of 100 samples each (12.5 milliseconds). As for the images, we employed 200 greyscale images sourced from various datasets, each with dimensions of $128\times 128$ pixels.

Regarding the atoms utilized with the speech dataset, we opted for Gabor atoms generated using the mathematical formula [26]:

$$\begin{equation*} \boldsymbol {\varphi }(g,t_{0},f)=\frac {1}{\sqrt {g}}e^{\frac {-\pi (t-t_{0})^{2}}{a^{2}}}\cos (2\pi f(t-t_{0})) \tag {34}\end{equation*}$$ Here, $g$ , $t_{0}$ , and f represent the scale, time shift, and frequency arguments respectively. It’s worth noting that these arguments were adjusted to obtain $\boldsymbol {\Phi } \in \mathbb {R}^{100\times 512}$ . As for the atoms used with the image datasets, we employed Discrete Cosine Transform atoms, resulting in a dictionary $\boldsymbol {\Phi } \in \mathbb {R}^{128\times 512}$ .

C. Performance Indexes

For the numerical results, we mainly focus on the following performance metrics:

• Compression percentage and quality assessment: The compression percentage can be calculated using Eq.(48). As discussed earlier, ODS represents the size in bits of the forward-modeled data, while CDS refers to the size in bits after backward processing. This study examines the impact of backward processing on compression percentage (CP) across various quality levels. For speech data, the Perceptual Evaluation of Speech Quality (PESQ) is employed as the primary quality assessment of modeled speech data. For image data, the Structural Similarity Index (SSIM) serves as the main quality assessment of image data.

• Significance test: In addition to the foregoing, a t-test has been conducted to investigate whether the observed improvements are significant.

• Complexity test: Finally, the computational complexity was calculated by measuring the time required by the algorithm to complete one iteration.

D. Results and Discussions

1) Case Study 1: K-Based Modeling

In this case study, the stopping criterion for forward modelling is based on a predefined sparsity level k, where iterations stop once this level is reached. For both speech and image data, we used nine sparsity levels, $k = 12:8:60$ . It should be noted that k is less than M, where M represents the dimension of the speech segment or image vector.

a: Results of Speech Data (Case Study 1)

For the $CP_{\%}$ results of OMP-based modelling (see Figure 7), OMP-H consistently outperforms both OMP-B and OMP-T across all PESQ values. Furthermore, OMP-B performs better than OMP-T across all PESQ values. When examining the enhancements gained, OMP-H achieves minimum and maximum enhancements of approximately 15.2% and 18.4% respectively, at PESQ levels of 2.7 and 4.2 respectively. With OMP-B, the enhancements are slightly lower at 14.5% and 17.7%, also occurring at PESQ levels of 2.7 and 4.2. For OMP-T, the minimum and maximum enhancements are 13% and 16.8% respectively, occurring at the same PESQ levels. Finally, the discrepancy between the analytical and simulation values of $\rho = Pr\left [{{r_{t} \gt \frac {r_{b}}{2}}}\right]$ (see Figure 7d) leads to the difference between the simulation and analytical values of $CP_{\%}$ as shown in Figure 7a.

FIGURE 7.

Results of the k-based modeling of speech data.

For the $CP_{\%}$ results of OOMP-based modelling (see Figure 7b), OOMP-H consistently outperforms both OOMP-B and OOMP-T across all PESQ values. Additionally, OOMP-B also performs better than OOMP-T across all PESQ values. When examining the enhancements achieved, OOMP-H yields minimum and maximum enhancements of approximately 8.8% and 14.6% respectively, at PESQ levels of 4.4 and 1.7. In contrast, OOMP-B achieves enhancements of 8.7% and 13.1% respectively at the same PESQ levels. OOMP-T shows lower minimum and maximum enhancements of 6.5% and 10.9% respectively at the same PESQ levels. Finally, the difference between the analytical and simulation values of $\rho$ (see Figure 7c) results in a difference between the simulation and analytical values of $CP_{\%}$ as shown in Figure 7b.

For the $CP_{\%}$ results of FBP-based modelling (see Figure 7c), FBP-H consistently outperforms both FBP-B and FBP-T across all PESQ values. Furthermore, FBP-B also performs better than FBP-T across all PESQ values. When examining the achieved enhancements, FBP-H gains minimum and maximum enhancements of approximately 12.8% and 15% respectively, occurring at PESQ levels of 2.7 and 4.3. In contrast, FBP-B achieves enhancements of 12.1% and 14.6% respectively, at PESQ levels of 2.4 and 4.3. With FBP-T, the minimum and maximum enhancements are 10.7% and 13.2% respectively, occurring at PESQ levels of 2.4 and 4.3. Finally, the difference between the analytical and simulation values of $\rho$ (see Figure 7f) leads to the differences between the simulation and analytical values of $CP_{\%}$ shown in Figure 7c.

In all three modelling approaches—OMP, OOMP, and FBP—the high-performance variants (H variants) consistently outperform their respective B and T counterparts across all PESQ values. OMP-H achieves the highest minimum and maximum enhancements, followed by FBP-H and OOMP-H. OMP-B and FBP-B perform better than OOMP-B, while OMP-T and FBP-T outperform OOMP-T. In general, the H variants provide the most substantial enhancements, with B variants offering moderate improvements and T variants achieving the least.

b: Results of Image Data (Case Study 1)

In the $CP_{\%}$ results of OMP-based modelling (see Figure 8a), OMP-H consistently outperforms both OMP-B and OMP-T across all SSIM values. Furthermore, OMP-T often outperforms OMP-B across most SSIM values. Examining the enhancements gained, OMP-H achieves minimum and maximum enhancements of approximately 18.3% and 20%, respectively, at SSIM levels of 0.8 and 0.98. In contrast, OMP-T attains enhancements of 16% and 19.5%, occurring at SSIM levels of 0.62 and 0.98. As for OMP-B, the minimum and maximum enhancements are 16.8% and 18.5%, occurring at SSIM levels of 0.8 and 0.98. Finally, the discrepancy between the analytical and simulation values of $\rho$ (see Figure 8d) leads to differences between the simulation and analytical values of $CP_{\%}$ , as shown in Figure 8a.

FIGURE 8.

Results of the k-based modeling of image data.

In the $CP_{\%}$ results of OOMP-based modelling (see Figure 8b), OOMP-H consistently outperforms both OOMP-B and OOMP-T across all SSIM values. Additionally, OOMP-T performs better than OOMP-B across most SSIM values. When examining the enhancements, OOMP-H achieves minimum and maximum enhancements of approximately 17.7% and 18.7% respectively, occurring at SSIM levels of 0.85 and 0.98. In contrast, with OOMP-T, these enhancements are 14.9% and 18.3% respectively, occurring at SSIM levels of 0.63 and 0.98. For OOMP-B, the minimum and maximum enhancements are 16.1% and 17.5% respectively, occurring at SSIM levels of 0.83 and 0.98. Finally, the difference between the analytical and simulation values of $\rho$ (see Figure 8e) leads to the differences between the simulation and analytical values of $CP_{\%}$ as shown in Figure 8b.

For the $CP_{\%}$ results of FBP-based modelling (see Figure 8c), FBP-H consistently outperforms both FBP-B and FBP-T across all SSIM values. Additionally, FBP-T performs better than FBP-B across most SSIM values. When examining the enhancements, FBP-H achieves minimum and maximum enhancements of approximately 18.3% and 19.5% respectively, at SSIM levels of 0.83 and 0.98. In contrast, with FBP-T, these enhancements are 15.5% and 19% respectively, at SSIM levels of 0.63 and 0.98. As for FBP-B, the minimum and maximum enhancements are 16.6% and 18% respectively, occurring at SSIM levels of 0.83 and 0.98. Finally, the discrepancy between the analytical and simulation values of $\rho$ (see Figure 8f) results in differences between the simulation and analytical values of $CP_{\%}$ , as shown in Figure 8c.

The analyses of the OMP, OOMP, and FBP modelling approaches show that the high-performance variants (H variants) consistently surpass their respective B and T counterparts across all SSIM values. These H variants provide larger compression enhancements compared to the other models, while the T variants typically outperform the B variants. Differences between the analytical and simulation values of $\rho$ result in inconsistencies in the simulation and analytical values of $CP_{\%}$ across all three approaches.

2) Case Study 2: Error-Based Modeling

In this case study, the stopping criterion for forward modelling is determined by a specified normalized error threshold $\epsilon$ at which point iterations cease once this level is attained. For speech data, nine normalized error levels were used, $\epsilon = 0.2:0.5:0.6$ . However, for image data, the normalized error levels employed were $\epsilon = 0.008:0.004:0.04$ .

a: Results of Speech Data (Case Study 2)

For the $CP_{\%}$ results of OMP-based modelling (see Figure 9a), OMP-H consistently outperforms both OMP-B and OMP-T until PESQ values reach 1.84, after which OMP-B becomes the superior performer. Examining the enhancements achieved, OMP-H attains minimum and maximum enhancements of approximately 16.4% and 19.8% respectively, at PESQ levels of 2 and 1.5. In contrast, OMP-B achieves enhancements of 16.6% and 21.2% respectively, at PESQ levels of 1.16 and 2.05. Meanwhile, OMP-T achieves minimum and maximum enhancements of 12.5% and 18% respectively, at PESQ levels of 2 and 1.6. Finally, the discrepancy between the analytical and simulation values of $\rho$ (see Figure 9d) results in differences between the simulation and analytical values of $CP_{\%}$ as shown in Figure 9a.

FIGURE 9.

Results of the error-based modeling of speech data.

For the $CP_{\%}$ results of OOMP-based modelling (see Figure 9b), OOMP-H consistently outperforms both OOMP-B and OOMP-T until PESQ values reach 1.66, at which point OOMP-B becomes the superior performer. When examining the enhancements achieved, OOMP-H achieves minimum and maximum enhancements of approximately 12.5% and 15.3% respectively, at PESQ levels of 2.08 and 1.18. In contrast, OOMP-B achieves enhancements of 14% and 17.8% respectively, at PESQ levels of 1.4 and 2.19. As for OOMP-T, both minimum and maximum enhancements are 8.8% and 12.1% respectively, occurring at PESQ levels of 2.08 and 1.5. Finally, the difference between the analytical and simulation values of $\rho$ (see Figure 9d) leads to discrepancies between the simulation and analytical values of $CP_{\%}$ shown in Figure 9a.

For the $CP_{\%}$ results of FBP-based modelling (see Figure 9b), FBP-H performs better than both FBP-B and FBP-T at lower PESQ levels, but it eventually becomes the worst performer. Upon examining the enhancements achieved, FBP-H exhibits minimum and maximum enhancements of about 6% and 17% respectively, occurring at PESQ levels of 2.05 and 1.25. In contrast, with FBP-B, the same maximum enhancement occurs at a PESQ level of 1.7, while the minimum enhancement of 14.3% occurs at a PESQ level of 2.19. Meanwhile, FBP-T achieves both minimum and maximum enhancements of 10.5% and 15.8% respectively, at PESQ levels of 2.16 and 1.6. Lastly, the difference between the analytical and simulation values of $\rho$ (see Figure 9f) causes the discrepancy between the simulation and analytical values of $CP_{\%}$ shown in Figure 9c.

In the analysis of $CP_{\%}$ results across different modelling approaches, OMP-based modelling initially sees OMP-H outperforming both OMP-B and OMP-T until PESQ values reach a certain threshold. After this point, OMP-B becomes the dominant performer, with notable enhancements in efficiency. Similarly, in the OOMP-based modelling approach, OOMP-H leads initially, then OOMP-B takes over at lower PESQ values. The analysis shows a clear trend where the B variants tend to outperform the H and T variants in efficiency, depending on the specific PESQ level being analysed.

The FBP-based modelling, however, follows a slightly different pattern. FBP-H is initially effective at lower PESQ levels, but it eventually becomes the least effective option. As a result, FBP-B and FBP-T emerge as the better choices at higher PESQ levels.

b: Results of Image Data (Case Study 2)

In the $CP_{\%}$ results of OMP-based modelling (see Figure 10a), OMP-H outperforms both OMP-B and OMP-T across all SSIM values. Additionally, OMP-T surpasses OMP-B for SSIM values above 0.73. Examining the enhancements, OMP-H shows minimum and maximum enhancements of around 12% and 19.8%, respectively, at SSIM levels of 0.51 and 0.94. Meanwhile, OMP-T achieves enhancements of 7% and 19.5% at SSIM levels of 0.52 and 0.95. In contrast, OMP-B achieves minimum and maximum enhancements of 10.5% and 17.6% at SSIM levels of 0.51 and 0.95. Lastly, differences between the analytical and simulation values of $\rho$ (see Figure 10d) lead to variations in the simulation and analytical values of $CP_{\%}$ as shown in Figure 10a.

FIGURE 10.

Results of the error-based modeling of image data.

For the $CP_{\%}$ results of OOMP-based modelling (see Figure 10b), OOMP-H consistently outperforms both OMP-B and OOMP-T across all SSIM values. Additionally, OOMP-T surpasses OOMP-B for SSIM values above 0.72. Examining the enhancements gained, OOMP-H achieves minimum and maximum enhancements of approximately 11.5% and 18.6%, respectively, at SSIM levels of 0.51 and 0.94. Meanwhile, OOMP-T attains minimum and maximum enhancements of 9.4% and 18.4% at the same SSIM levels. In contrast, OOMP-B achieves minimum and maximum enhancements of 11.8% and 16.8% respectively, at SSIM levels of 0.51 and 0.94. Finally, the discrepancy between the analytical and simulation values of $\rho$ (see Figure 10e) leads to differences between the simulation and analytical values of $CP_{\%}$ shown in Figure 10b.

In the $CP_{\%}$ results of FBP-based modelling (see Figure 10c), FBP-H consistently outperforms both FBP-B and FBP-T across all SSIM values. Additionally, FBP-T performs better than FBP-B for SSIM values above 0.7. Examining the enhancements achieved, FBP-H gains minimum and maximum enhancements of around 10.9% and 19.5% respectively, at SSIM levels of 0.51 and 0.94. In contrast, FBP-T achieves minimum and maximum enhancements of 9.2% and 19% respectively, at the same SSIM levels. As for FBP-B, it achieves minimum and maximum enhancements of 9.2% and 17.3% respectively, also at SSIM levels of 0.51 and 0.94. Finally, the difference between the analytical and simulation values of $\rho$ (see Figure 10f) results in differences between the simulation and analytical values of $CP_{\%}$ as shown in Figure 10c.

Summing up, in the analysis of OMP-based modelling, OMP-H performs the best across all SSIM values and OMP-T outperforms OMP-B for SSIM values above a certain threshold. OMP-H achieves higher enhancements compared to the other methods. In the analysis of OOMP-based modelling, OOMP-H is also the most effective across all SSIM values, with OOMP-T performing better than OOMP-B for SSIM values above a similar threshold. OOMP-H shows greater improvements than the other methods. For FBP-based modelling, FBP-H leads across all SSIM values, with FBP-T outperforming FBP-B for SSIM values above a certain level. FBP-H yields the most significant enhancements.

3) Statistical Assessment

In the k-based modelling, the heat map matrix in Figure 11 illustrates the significance test of the CP results for all variants: -B, -T, and -H. Yellow cells indicate when the CP values obtained by the algorithm on the vertical axis are significantly higher $(p \leq 0.05)$ than those of the algorithm on the horizontal axis. In the speech data results (see Figure 11a), OMP-H demonstrates the most significant improvements, followed by FBP-H and OMP-B. The least significant enhancements are seen with OOMP-T, OOMP-B, and OOMP-H. In the image data results (see Figure 11b), OMP-H also shows the most significant improvements, followed by FBP-H and OMP-T. The least significant enhancements are found with OOMP-B, FBP-B, and OMP-B.

FIGURE 11.

T-Test results for k-based modeling.

In the error-based modelling, the heat map matrix in Figure 12 illustrates the significance test of the CP results for all variants: -B, -T, and -H. In the speech data results (see Figure 11a), OOMP-H demonstrates the most significant improvements, followed by OOMP-B and OOMP-T. The least significant enhancements are seen with FBP-T, FBP-B, and FBP-H. In the image data results (see Figure 11b), OOMP-H also shows the most significant improvements, followed by FBP-H and OMP-H. The least significant enhancements are found with OMP-B, OMP-T, and FBP-B.

FIGURE 12.

T-Test results for error-based modeling.

4) Computation Time

To validate the complexity analysis of T-BRe discussed in section III-C, we measured the time spent per backward iteration. We focused only on the iteration time for both B-BRe and T-BRe since H-BRe is assumed to operate both algorithms in parallel, making the total time consumed equivalent to the maximum time taken by either algorithm. Note that the simulation environment specifications are provided in section V-A.

Figure 13 presents the log scale of the collected measurements. As illustrated, the backward iteration in B-BRe takes approximately $0.2~msec$ , while in T-BRe, it requires about $3 msec$ , which is 15 times longer than B-BRe. The significant increase in iteration time is due to the processing of the three-dimensional data structure $\Upsilon$ (as shown in Figure 3), whereas B-BRe only handles a two-dimensional size.

FIGURE 13.

Time consumed by both B-BRe and T-BRe algorithms.

SECTION VI. Limitations and Applicability

When examining the limitations of both T-BRe and H-BRe, the primary concern lies in their time complexity. As discussed in section V-D4, the complexity of the backward replacement approach hinges on the dimensions of the data structure $\Upsilon$ , which is three-dimensional in T-BRe and two-dimensional in B-BRe (see Figure 3). Moreover, the correlation between achieved compression and quality levels is linked to the forward modeling algorithm utilized in the initial stage of backward processing. Therefore, the overall performance is not solely determined by the recommended backward approach.

Another noteworthy limitation is that backward replacement errors, as delineated in section III-A, are minimized locally, implying that the error from replacing three coefficients is minimized within the space spanned by the corresponding atoms. This limitation indicates potential future research avenues aimed at minimizing replacement errors globally across the space spanned by all atoms selected during forward modeling.

Additionally, the results discussed and analyzed in section V-D are closely tied to and influenced by the type of atoms utilized in the simulation study, which are mathematically generated. This limitation underscores the need for further investigation in future endeavors to expand simulations by incorporating other types of atoms, such as those generated based on data.

Lastly, the mathematical analysis of H-BRe presented in section IV is limited by the assumption that the random behavior of both $r_{b}$ and $r_{t}$ variables follows a linear distribution. This assumption was made to simplify the overall analysis of the H-BRe algorithm’s performance.

Regarding the applicability of the proposed variants of the backward replacement approach, it is evident that the compression capabilities of the forward greedy pursuit algorithms are enhanced. However, to fully leverage these enhancements for comparison with traditional speech or image compression techniques, it is necessary to apply lossless compression at the end phase of the encoder before transmitting the encoded data. Therefore, in future work, the intention is to apply lossless compression and then compare the obtained compression levels with traditional techniques.

SECTION VII. Conclusion and Future Works

The paper proposes two variants of the backward replacement approach, T-BRe and H-BRe, to enhance the compression capabilities of forward greedy pursuit algorithms. The study evaluates the effectiveness of these methods using three algorithms (OMP, OOMP, and FBP) and conducts simulations with different types of data (image and speech) using a mathematically generated dictionary. Additionally, the paper provides a mathematical analysis of the H-BRe algorithm to validate its effectiveness and identify its limitations.

Analysis and simulations demonstrate that H-BRe significantly improves the compression capabilities of forward greedy pursuit algorithms. The enhancements depend on factors such as the forward modelling technique, stopping criterion, and the randomness of variables $r_{t}$ and $r_{b}$ . The H variants prove most effective in various modelling approaches and metrics, including PESQ and SSIM values, while B and T variants are efficient in some scenarios.

However, the methods have limitations such as time complexity, local error minimization, dependency on atom types, and the assumption of linear distribution in the mathematical analysis. Suggested future works include optimizing time complexity, improving compression-quality balance, minimizing replacement errors globally, exploring different types of atoms, and revising assumptions in mathematical analysis for a more nuanced understanding of H-BRe’s performance.

ACKNOWLEDGMENT

A. N. Omara is deeply grateful to the Datacenter Team at ERI for their invaluable assistance throughout this research. Their generous provision of essential resources was crucial in facilitating the successful execution of my simulations. Without their steadfast support and dedication to academic pursuits, this study would not have been possible. He sincerely appreciate their outstanding professionalism.

Appendix A Proof of Theorem 1

To minimize the error function $\lVert \boldsymbol {e}\rVert ^{2}_{2}$ in Eq. (5), the error vector should be orthogonal to the sum vector, i.e., $\boldsymbol {e} \perp \boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T}$ . Let’s first find the inner product formula between $\boldsymbol {e}$ and $\boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T}$ .

$$\begin{align*} \boldsymbol {e}^{T} \boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T} & =\bigg (\boldsymbol {\Phi }_{x,y,z} \boldsymbol {W}^{T}_{x,y,z} - \boldsymbol {\Phi }_{x,y,z} \boldsymbol {I}^{T} W'_{x,y,z}\bigg)^{T}\boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T} \\ & =\bigg (\boldsymbol {W}_{x,y,z}\boldsymbol {\Phi }^{T}_{x,y,z} - W'^{T}_{x,y,z}\boldsymbol {I} \boldsymbol {\Phi }_{x,y,z}^{T} \bigg)\boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T} \\ & = \boldsymbol {W}_{x,y,z}\boldsymbol {\Phi }^{T}_{x,y,z}\boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T} - W'^{T}_{x,y,z}\boldsymbol {I}\boldsymbol {\Phi }_{x,y,z}^{T} \boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T} \tag {35}\end{align*}$$ To achieve the condition $\boldsymbol {e} \perp \boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T}$ , then $\boldsymbol {e}^{T} \boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T} = 0$ , and the unique value of $W'_{x,y,z}$ that achieves the condition is $$\begin{equation*} W'_{x,y,z} = \frac {\boldsymbol {W}_{x,y,z}\boldsymbol {\Phi }^{T}_{x,y,z}\boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T}}{\boldsymbol {I}\boldsymbol {\Phi }_{x,y,z}^{T} \boldsymbol {\Phi }_{x,y,z}\boldsymbol {I}^{T}} \tag {36}\end{equation*}$$

Assume the subscript $x,y,z$ is replaced with $\gamma$ . The minimum replacement error can be obtained by substituting $W'_{\gamma }$ in (5) as follows, shown in the equation at the bottom of the page.

$$\begin{align*} \lVert \boldsymbol {e}\rVert ^{2}_{2} & =\bigg \lVert \boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }- \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T} \frac {\boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}\bigg \rVert ^{2}_{2} \\ & = \left ({{ \boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }- \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T} \frac {\boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}}}\right)^{T} \left ({{ \boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }- \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T} \frac {\boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}}}\right) \\ & = \left ({{ \boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }- \frac {I \boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}I \boldsymbol {\Phi }^{T}_{\gamma }}}\right) \left ({{ \boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }- \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T} \frac {\boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}}}\right) \\ & = \boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }- \boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T} \frac {\boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}} - \frac {I \boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}I \boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }+ \frac {I \boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {W}^{T}_{\gamma }}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}I \boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T} \frac {\boldsymbol {W}_{\gamma }\boldsymbol {\Phi }^{T}_{\gamma }\boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}{\boldsymbol {I}\boldsymbol {\Phi }_{\gamma }^{T} \boldsymbol {\Phi }_{\gamma }\boldsymbol {I}^{T}}\end{align*}$$

Hence, it is proved.

Appendix B Proof of Theorem 4

For the linearly distributed random variable $0 \le r \le r_{m}$ , the distribution function could be written as follows:

$$\begin{equation*} f(r) = a r + b \tag {37}\end{equation*}$$ $\because \sum _{r=0}^{r_{m}}f(r) = 1$ , we have: $$\begin{align*} \sum _{r=0}^{r_{m}} \left ({{ ar+b}}\right) & = 1 \tag {38}\\ \therefore \ b & = \frac {1}{r_{m} + 1} {-} a \frac {r_{m}}{2} \tag {39}\\ \therefore \ f(r)& = a\left ({{r - \frac {r_{m}}{2}}}\right)+\frac {1}{r_{m} + 1} \tag {40}\end{align*}$$ The bounds of a could be found by the fact that a has maximum positive value when $f(0)=0$ and has maximum negative value when $f(r_{m}) = 0$ . Therefore, by substituting in (40), we get: $$\begin{equation*} \frac {-2}{r_{m}(r_{m} + 1)} \lt a \lt \frac {2}{r_{m}(r_{m} + 1)} \tag {41}\end{equation*}$$ According to the assumption that both $r_{b}$ and $r_{t}$ are two independent variables, then the joint probability $f(r_{b},r_{t}) = f(r_{b}) f(r_{t})$ . To find $\rho = Pr\left ({{r_{t}\gt \frac {r_{b}}{2} }}\right)$ , we can write the following: $$\begin{align*} \rho & = \mathop {\sum }\limits _{r_{b} = 0}^{\frac {k}{2}} \mathop {\sum }\limits _{r_{t} = r_{b}/2+1}^{\frac {k}{3}} f(r_{b})f(r_{t}) \\ \rho & = \mathop {\sum }\limits _{r_{b} = 0}^{\frac {k}{2}} \ f(r_{b}) \mathop {\sum }\limits _{r_{t} = \frac {r_{b}}{2}+1}^{\frac {k}{3}} f(r_{t}) \tag {42}\end{align*}$$ For T-BRe, we have $f(r_{t}) = a_{t} \left ({{r_{t} - \frac {k}{6}}}\right) + \frac {3}{k+3}$ , so the summation $\sum _{r_{t} = \frac {r_{b}}{2}+1}^{\frac {k}{3}} f(r_{t})$ could be found as follows: $$\begin{align*} \mathop {\sum }\limits _{r_{t} = \frac {r_{b}}{2}+1}^{\frac {k}{3}} f(r_{t}) & = \frac {a_{t}}{2}\left ({{ \frac {k}{3}- \frac {r_{b}}{2}}}\right)\left ({{ \frac {k}{3}+ \frac {r_{b}}{2}+1}}\right) \\ & \quad - \frac {k \ a_{t}}{6} \left ({{ \frac {k}{3} - \frac {r_{b}}{2}}}\right) +\frac {3}{k+3}\left ({{\frac {k}{3} - \frac {r_{b}}{2} }}\right) \\ & = A_{1} r_{b}^{2} + A_{2} r_{b} + A_{3} \tag {43}\end{align*}$$ where, $$\begin{align*} A_{1} & = - \frac {1}{8}a_{t} \tag {44}\\ A_{2} & = \frac {k-3}{12}a_{t} - \frac {3/2}{k+3} \tag {45}\\ A_{3} & = \frac {k}{6} a_{t} + \frac {k}{k+3} \tag {46}\end{align*}$$

For B-BRe, we have $f(r_{b}) = a_{b} \left ({{r_{b} - \frac {k}{4}}}\right) + \frac {2}{k+2}$ . In addition that, by substituting (43) in (42), we get, (47), as shown at the bottom of the page,

$$\begin{align*} \rho & = {\sum }_{r_{b} = 0}^{\frac {k}{2}} \left [{{ \left ({{B_{1} r_{b} + B_{2} }}\right) \left ({{A_{1} r_{b}^{2} + A_{2} r_{b} + A_{3} }}\right)}}\right ] \\ & = {\sum }_{r_{b} = 0}^{\frac {k}{2}}\left [{{ \left ({{A_{1} B_{1}}}\right)r_{b}^{3} + \left ({{A_{1} B_{2} + A_{2} B_{1}}}\right)r_{b}^{2} + \left ({{A_{2} B_{2}+A_{3} B_{1}}}\right)r_{b} + A_{3} B_{2}}}\right ] \\ & = A_{1} B_{1} \left ({{\frac {\frac {k}{2}\left ({{\frac {k}{2} + 1}}\right)}{2}}}\right)^{2} + (A_{1} B_{2} + A_{2} B_{1}) \frac {\frac {k}{2}\left ({{\frac {k}{2} + 1}}\right)(k + 1)}{6} + \ (A_{2} B_{2} + A_{3} B_{1}) \frac {\frac {k}{2}\left ({{\frac {k}{2} + 1}}\right)}{2} + A_{3} B_{2} \left ({{\frac {k}{2} + 1}}\right) \\ & = A_{1} B_{1} \left ({{ \frac {k^{4}+4k^{3}+4k^{2}}{64}}}\right) + (A_{1} B_{2} + A_{2} B_{1}) \left ({{\frac {k^{3} + 3k^{2}+2k}{24}}}\right) + \ (A_{2} B_{2} + A_{3} B_{1}) \left ({{\frac {k^{2}+2k}{8}}}\right) \\ & \quad + A_{3} B_{2} \left ({{\frac {k}{2} + 1}}\right) \tag {47}\end{align*}$$ where, $$\begin{align*} B_{1} & = a_{b} \\ B_{2} & = - \frac {k}{4} a_{b} +\frac {2}{k+2}\end{align*}$$ By substituting in (47), $\rho$ could be written as a function of $a_{b}$ , $a_{t}$ and $k$ as follows, shown in the equation at the bottom of the page. $$\begin{align*} \rho & = - \left ({{ \frac {k^{4}+4k^{3}+4k^{2}}{512}}}\right)a_{b} a_{t} + \left ({{ \frac {11k-24}{96}a_{b} a_{t} - \frac {3/2}{k+3} a_{b} - \frac {1}{4k+8} a_{t}}}\right) \left ({{\frac {k^{3} + 3k^{2}+2k}{24}}}\right) \\ & \quad + \ \left ({{ \frac {-k^{2}+11k}{48} a_{b} a_{t} + \frac {11k}{8k+24} a_{b} + \frac {k-3}{6k+12} a_{t} - \frac {3}{k^{2} + 5k + 6} }}\right) \left ({{\frac {k^{2}+2k}{8}}}\right) \\ & \quad + \ \left ({{\frac {-k^{2}}{24} a_{b} a_{t} - \frac {k^{2}}{4k+12} a_{b} + \frac {k}{3k+6} a_{t} + \frac {2k}{k^{2} + 5k + 6} }}\right) \left ({{\frac {k}{2} + 1}}\right) \\ & = \left ({{\frac {k^{4}-6k^{3}-64k^{2}-96k}{4608}}}\right) a_{b} a_{t}-\left ({{\frac {k^{3}+6k^{2}+8k}{64k+192}}}\right) a_{b} + \left ({{\frac {3k^{2} + 19k }{192}}}\right) a_{t} + \frac {5k}{8k+24}\end{align*}$$

Hence, it is proved.

Appendix C Proof of Theorem 8

The compression percentage of H-BRe can be represented mathematically as follows:

$$\begin{equation*} \mathcal {CP}_{H} = \left [{{1-\frac {\text {Compressed data size (CDS)}}{\text {Origional data size (ODS)}}}}\right ] \times 100\% \tag {48}\end{equation*}$$

As known previously the ODS is the sum of number of bits assigned to k indices and coefficients. So,

$$\begin{equation*} \text {ODS} = k(B_{i} + B_{c}) \tag {49}\end{equation*}$$ As for the CDS, H-BRe has two options, it either selects B-BRe or T-BRe according to a predefined condition. So, we have two possible values for CDS, either $\text {CDS}_{B}$ for B-BRe, or $\text {CDS}_{T}$ for T-BRe. Therefore, the expected value of CP or $E\{\mathcal {CP}_{H}\} = {\mathcal {CP}_{H}}$ could be written as follows: $$\begin{equation*} {\mathcal {CP}}_{H} = \left [{{1- \frac {(1-\rho)E\{\text {CDS}_{B}\}+\rho E\{\text {CDS}_{T}\}}{k\left ({{ B_{i} + B_{c}}}\right) }}}\right ] \tag {50}\end{equation*}$$ For $E\{\text {CDS}_{B}\}$ , the formula in (12) can be rewritten in terms of the expectation operator E as follows: $$\begin{align*} E\{\text {CDS}_{B}\} & = \left ({{ k - E\{r_{b}\}}}\right) B_{c} + k B_{i} \\ & = \left ({{ k - \sum _{r_{b}=0}^{k/2} r_{b} f(r_{b})}}\right) B_{c} + k B_{i} \\ & = \left ({{\frac {3k}{4} - \frac {a_{b} k}{12} - \frac {a_{b} k^{2}}{16} - \frac {a_{b} k^{3}}{96}}}\right) B_{c} + k B_{i} \tag {51}\end{align*}$$ As for $E\{\text {CDS}_{T}\}$ , the formula in (13) can be rewritten in terms of the expectation operator E as follows: $$\begin{align*} E\{\text {CDS}_{T}\} & = \left ({{ k - 2E\{r_{t}\}}}\right) B_{c} + k B_{i} \\ & = \left ({{ k - 2\sum _{r_{t}=0}^{k/3} r_{t} f(r_{t})}}\right) B_{c} + k B_{i} \\ & = \left ({{\frac {2k}{3} - \frac {a_{t}k}{9} - \frac {a_{t}k^{2}}{18} - \frac {a_{t}k^{3}}{162}}}\right) B_{c} + k B_{i} \tag {52}\end{align*}$$

By substituting (51) and (52) in (50), we get, (53), as shown at the top of the next page.

$$\begin{align*} \frac {{\mathcal {CP}}_{H}}{100} & = 1- \frac {k B_{i} + \frac {3k}{4} - \frac {a_{b} k}{12} - \frac { \rho k }{12} - \frac {a_{b} k^{2}}{16} - \frac {a_{b} k^{3}}{96} + \frac {\rho a_{b} k }{12} - \frac {\rho a_{t} k }{9} + \frac {\rho a_{b} k^{2}}{16} + \frac {\rho a_{b} k^{3} }{96} - \frac {\rho a_{t} k^{2} }{18} - \frac {\rho a_{t} k^{3}}{162}}{k\left ({{ B_{i} + B_{c}}}\right) } \\ \frac {{\mathcal {CP}}_{H}}{100} & = \frac { \left [{{\left ({{ \frac {(1-\rho)a_{b}}{96}+\frac {\rho a_{t}}{162} }}\right)k^{2} + \left ({{ \frac {(1-\rho)a_{b}}{16}+\frac {\rho a_{t}}{18}}}\right)k - \left ({{\frac {(1-\rho)(9-a_{b})}{12}+\frac {\rho (6-a_{t})}{9}-1 }}\right)}}\right ] B_{c}}{\left ({{ B_{i} + B_{c}}}\right) } \tag {53}\end{align*}$$

Hence, it is proved.