# Error in the Reconstruction of Nonsparse Images

Authors: Miloš Brajović; Isidora Stanković; Miloš Daković; Cornel Ioana; Ljubiša Stanković
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Sparse signals, assuming a small number of nonzero coefficients in a transformation domain, can be reconstructed from a reduced set of measurements. In practical applications, signals are only approximately sparse. Images are a representative example of such approximately sparse signals in the two-dimensional (2D) discrete cosine transform (DCT) domain. Although a significant amount of image energy is well concentrated in a small number of transform coefficients, other nonzero coefficients appearing in the 2D-DCT domain make the images be only approximately sparse or nonsparse. In the compressive sensing theory, strict sparsity should be assumed. It means that the reconstruction algorithms will not be able to recover small valued coefficients (above the assumed sparsity) of nonsparse signals. In the literature, this kind of reconstruction error is described by appropriate error bound relations. In this paper, an exact relation for the expected reconstruction error is derived and presented in the form of a theorem. In addition to the theoretical proof, the presented theory is validated through numerical simulations.


---

## Body

## 1. Introduction

Signals that can be characterized by a small number of nonzero coefficients are referred to as sparse signals [1–11]. These signals can be reconstructed from a reduced set of measurements [1–25]. The measurements represent linear combination of the sparsity (transform) domain coefficients [1, 7, 24]. Signal samples can be considered as measurements (observations) in the case when a linear signal transform is the sparsity domain. Signal sparsity in a transformation domain can be observed in a number of important applications. For example, ISAR images are commonly sparse in the two-dimensional Fourier transform domain, whereas digital images are well known for their good concentration in the domain of two-dimensional (2D) discrete cosine transform (DCT) [8, 21–24].The idea of reduced number of observations is studied within the compressed sensing (CS) theory and the sparse signal processing framework. The reduced number of measurements may appear due to different causes. In the CS applications, it arises as a consequence of intentional sampling strategy, aiming to reduce the signal acquisition time, equipment load, and subject exposure to potentially dangerous radiation during the acquisition in biomedical applications, or, simply, there is a particular interest to reduce the amount of acquired samples while preserving the complete information (compression) [1–15]. In certain cases, physical unavailability can be a cause of a reduced number of measurements. In many applications, strong disturbances (noise) can significantly corrupt the signal samples. Such signals are processed by detecting and intentionally neglecting the corrupted measurements [7, 9, 23]. Regardless of their unavailability reasons, under certain reasonable conditions, missing samples can be reconstructed using well developed CS methods and algorithms [1, 2].The DCT is an important and frequently used tool in signal processing [21–27]. Many signal classes can be more compactly represented in the DCT domain than in the Fourier domain. Due to its superior compressibility, the 2D-DCT is one of the most exploited transforms in the compression of digital images [24]. Moreover, this transform domain has been convenient for the reconstruction of digital images with missing pixels and/or noise corruption using the sparsity assumption [21–23]. Measuring the 2D-DCT coefficients concentration (using the l1-norm based measure) and varying missing samples values to obtain the sparsest possible solution leads to the prominent compressive sensing reconstruction results [20, 23]. In the orthogonal matching pursuit (OMP) framework, successful reconstruction is easily obtained if the coefficients corresponding to signal component positions are successfully identified [12, 28–30]. In that case, the true coefficient values can be calculated using the identified component positions and the 2D-DCT measurement matrix [9, 24]. However, it is important to note that, in practice, digital images are usually only approximately sparse or nonsparse in the 2D-DCT domain [21–24]. It means that besides the coefficients with significant values, carrying most of the signal energy, small valued coefficients may appear instead of zero-valued ones. As sparse recovery algorithms assume certain sparsity level, these coefficients will remain unreconstructed [8, 24]. This leads to inevitable reconstruction errors. The reduction of the amount of available samples manifests as a transform domain noise [7, 9]. During the reconstruction, this noise is completely cancelled out, if the sparsity assumption is strictly satisfied. However, if weak signal coefficients of a nonsparse signal remain unreconstructed, their contribution to the noise in the reconstructed coefficients remains. If a nonsparse signal is reconstructed with a reduced set of available samples, then the noise due to the missing samples in unreconstructed coefficients will be considered as an additive input noise in the reconstructed signal [8].The existing compressive sensing literature provides only the general bounds for the reconstruction error for nonsparse signals (reconstructed with the sparsity assumption) [1, 2, 4, 5, 28]. The error bounds for the DFT and DCT are considered in [6] within the reconstruction uniqueness framework. In this paper, we present an exact relation for the expected squared error in approximately sparse or nonsparse signals in the 2D-DCT domain. It is assumed that these signals are reconstructed from a reduced set of observations, under the sparsity constraint. Missing measurements influence on the transform domain is modelled by an additive noise [7]. The noise originating from missing samples in each signal component is statistically modelled as a Gaussian stochastic process, and its mean-value and variance are determined. The results are further exploited in the derivation of the relation for the error in the reconstructed signal if the sparsity assumption is used for the reconstruction of nonsparse signals. The theory is illustrated and verified by numerical results.The paper is organized as follows. Basic definitions regarding the 2D-DCT domain are provided in Section2. In Section 3, the main result is presented in the form of a theorem which will be examined and proved in the next sections. In Section 4, the 2D-DCT transform is put into the framework of the reduced number of observations and the error of nonsparse images reconstruction is analyzed. In Section 5, the theory is validated with several numerical examples, while the concluding remarks are given at the end of the paper, along with Appendix with special cases.


## 2. Basic Definitions

Consider a 2D discrete signal (digital image) of sizeM×N denoted by s(m,n). The 2D-DCT of this signal is defined by [24](1)Cp,q=∑m=0M-1∑n=0N-1sm,nφMm,pφNn,q,where p=0,…,M-1 and q=0,…,N-1 are the transform coefficient indices, and(2)φMm,p=2Mcos⁡π2m+1p2M,p≠0φNn,q=2Ncos⁡π2n+1q2N,q≠0are the normalized basis functions. For p=0 or q=0 these functions are of the form φM(m,0)=1/M and φN(n,0)=1/N, respectively. The corresponding inverse transform is given by(3)sm,n=∑p=0M-1∑q=0N-1Cp,qφMm,pφNn,qwith m=0,…,M-1,  n=0,…,N-1. The 2D-DCT transform can be written in a matrix form as [24](4)C=Φs,where C is the 2D-DCT coefficients matrix, Φ is 2D-DCT transformation matrix, and s is the matrix containing pixel values of a digital image. For the inverse 2D-DCT the relation s=ΨC holds, with Ψ=Φ-1.An image of the form(5)sm,n=∑l=1KAlφMm,plφNn,qlis sparse in the 2D-DCT domain if the number of nonzero 2D-DCT coefficients K is much smaller than the number of image pixels; that is, K≪MN. The components are located at the DCT indices (pl,ql) with amplitudes Al,  l=1,2,…,K.Assume that onlyNA≤MN randomly positioned pixels at (mi,ni)∈m1,n1,m2,n2,…,mNA,nNA = NA⊆N = 0,0,0,1,…,M-1,N-1 are available. If we rearrange the available pixels y into a vector with elements (6)yi=smi,ni=∑p=0M-1∑q=0N-1Cp,qφMmi,pφNni,q,where i=0,1,…,NA, we can write it in the matrix form as(7)y=ACrepresenting the mathematical model for the compressive sampling procedure, where A is an NA×MN measurement matrix. It is defined as the partial inverse 2D-DCT matrix, containing rows of Ψ that correspond to the available pixel positions.Compressive sensing reconstruction inherently assumes the signal sparsity. An images(m,n) is K-sparse in the 2D-DCT domain if only K of its 2D-DCT coefficients assume nonzero values. The nonzero coefficients at the positions (p,q)∈ΠK = {(p1,q1),(p2,q2),…,(pK,qK)} will be defined as CK.The 2D-DCT of an image reconstructed under theK-sparsity assumption will be denoted by CR. This is a vector with K reconstructed nonzero coefficients at (p,q)∈ΠK.An image is approximately sparse or nonsparse if the coefficientsC(p,q), (p,k)∉ΠK are small or of the same order as the coefficients C(p,q), (p,k)∈ΠK, respectively. In that case, the vector CK contains K largest values of C. The vector CK zero-padded up to the size of the original C and written in the same format as C will be denoted by CK0.


## 3. Reconstruction Error Energy

The main result of the paper providing the exact formulation of the expected squared reconstruction error in the case of nonsparse images will be given in the form of a theorem.Theorem 1.
Assume an image nonsparse in the 2D-DCT domain, with largest amplitudesAl,  l=1,2,…,K. Assume that only NA out of total MN samples are available, where 1≪NA<MN. Also assume that the image is reconstructed under the assumption as it was K-sparse. The energy of error in the K reconstructed coefficients CK-CR22 is related to the energy of unreconstructed components CK0-C22 coefficients as follows:(8)CK-CR22=KMN-NANAMN-1CK0-C22,where(9)CK-CR22=KMN-NANAMN-1∑l=K+1MNAl2,CK0-C22=∑l=K+1MNAl2.The theorem will be proved in the next section.


## 4. The Reconstruction Process and the Proof

The proof will be presented through four subsections. In the first subsection, we will define the 2D-DCT transform put into the framework of the reduced number of observations. Then, we will describe how the missing pixels affect other components in mono- and multicomponent cases, respectively. Finally, the reconstruction under the assumption that the signal isK-sparse is considered.


### 4.1. Initial Estimate

The initial (norm-two based) 2D-DCT estimation uses the available pixels only(10)C0p,q=∑m,n∈NAsm,nφMm,pφNn,q,where p=0,1,…,M-1,  q=0,1,…,N-1. The same results are obtained if the missing (unavailable) pixels assume zero values [7]. In a matrix form we can write(11)C0=ATy.The coefficients in (10) act as random variables, with different statistical properties at positions of the image components, (p,q)=(pl,ql), and positions not corresponding to image components, (p,q)≠(pl,ql).


### 4.2. Noise-Only Coefficients in Monocomponent Signals

We will first observe the monocomponent signal case, that is, whenK=1, and then generalize the result for multicomponent signals. Without loss of generality, we will assume that the amplitude is A1=1. From (5) and (10) we get (12)C0p,q=∑m,n∈NAφMm,p1φNn,q1φMm,pφNn,q.The variable(13)xp1q1m,n,p,q=φMm,p1φNn,q1φMm,pφNn,qis random for random values of (m,n). Its statistical properties for (p,q)≠(p1,q1) are studied next. Special cases are considered in Appendix. The initial 2D-DCT estimate can be written in the form(14)C0p,q=∑m,n∈NAxp1q1m,n,p,q.When(p,q)≠(p1,q1), the 2D-DCT coefficients correspond to nonsignal (noise) position and C0(p,q) behaves as a random Gaussian variable [7]. Using the basis functions orthogonality(15)∑m=0M-1∑n=0N-1xp1q1m,n,p,q=δp-p1,q-q1and the fact that values of xp1q1(m,n,p,q) are equally distributed, it can be concluded that the mean-value of C0(p,q) is equal to zero:(16)μC0p,q=EC0p,q=0,p,q≠p1,q1.In the case of the coefficient corresponding to the image component, using the same orthogonality property and the assumption of equal distribution of valuesxp1q1(m,n,p,q), it follows that(17)μC0p,q=EC0p,q=NAMN,p,q=p1,q1.For the zero-mean random variable, the variance definition is(18)σC0p,q2=E∑m,n∈NAxp1q12m,n,p,q+∑m,n∈NA∑i,j∈NAi,j≠m,nxp1q1m,n,p,qxp1q1i,j,p,q.As in the case when(p,q)≠(p1,q1) is observed, it can be concluded that(19)∑m=0M-1∑n=0N-1xp1q1m,n,p,q=0.Multiplying the left and right side of (19) by xp1q1(i,j,p,q) and taking the expectation of both sides we get(20)E∑m=0M-1∑n=0N-1xp1q1m,n,p,qxp1q1i,j,p,q=0,with (i,j)∈N. Values xp1q1(m,n,p,q) are equally distributed. Therefore, terms Exp1q1m,n,p,qxp1q1i,j,p,q for (m,n)≠(i,j) are the same and equal to a constant D. The total number of these terms is MN-1. Further, based on (20) we get(21)MN-1D+Exp1q12m,n,p,q=0.The initial variance definition can be written as(22)σC0p,q2=NAExp1q12m,n,p,q+NA2-NAD,as there are exactly NA expectations with quadratic terms in the first summation and NA(NA-1) terms in the second variance summation equal to D. In order to determine the unknown term Exp1q12(m,n,p,q), several special cases should be taken into account. Special cases of the 2D-DCT indices are considered in Appendix.Consider the general case whenp≠p1,  p≠M-p1,  q≠q1,  q≠N-q1 are satisfied. Then(23)Exp1q12m,n,p,q=EφM2m,p1φN2n,q1×EφM2m,pφN2n,q=1M2N2holds. Incorporating this result into (21) we get that (24)D=-1M2N21MN-1.Further, based on (22) the variance can be written as(25)σC0p,q2=NAMN-NAM2N2MN-1.This result also holds when (p1,q1) = (0,0). Note that when A1≠1, the result is multiplied by A12.It can be easily concluded that the average value of the variance (A.12) when all special cases from Appendix are included is constant and equal to(26)σ¯C02=A12NAMN-NAM2N2MN-12MN-214.As MN≫1, an accurate approximation for the average variance of noise-only coefficients follows(27)σN2=σ¯C02≈A12NAMN-NAM2N2MN-1.


### 4.3. Noise-Only Coefficients in Multicomponent Signals

In the multicomponent signal case, the observed random variable becomes(28)C0p,q=∑m,n∈NA∑l=1KAlφMm,plφNn,ql×φMm,pφNn,q.In this case, the coefficients at noise-only positions(p,q)≠(pl,ql) are random variables Gaussian in nature and zero-mean, as they are formed as the summation of independent zero-mean Gaussian variables over l. Namely, now the missing pixels in each image component contribute to the noise, and the noise originating from each component is proportional to the squared amplitude of that component, following (27) with Al,l=1,…,K. Therefore, 2D-DCT coefficients mean-value for a multicomponent signal (image) can be written as(29)μC0p,q=NAMN∑l=1KAlδp-pl,q-ql.The average variance of noise-only coefficients in this case easily follows(30)σ¯C02=∑l=1KAl2NAMN-NAM2N2MN-1.However, it is important to mention that components of the image multiplied with basis functions may cause a coupling effect if they are placed at positions satisfying certain conditions. Consequently, this effect may cause the increase of the previously derived variance at these positions. However, if it appears, for example, at the position(p1,q1) then the variance will be decreased for the same amount at the position (M-p1,N-q1). Therefore, we can further neglect this effect and assume that the variance expression in (30) holds in mean, which is crucial for the following derivation of the error in the nonsparse image reconstruction.


### 4.4. Nonsparse Signal Reconstruction

We consider that an image is reconstructed under the assumption that it isK-sparse and that it satisfies the condition for unique reconstruction in the compressive sensing theory. The number of reconstructed components is K. According to (30), each unreconstructed component in the image behaves as a Gaussian input noise with variance(31)σN2=Al2NAMN-NAM2N2MN-1.Therefore, allMN-K unreconstructed components will behave as a noise with variance(32)σT2=∑l=K+1MNAl2NAMN-NAM2N2MN-1.After reconstruction, the total noise energy from the unreconstructed components (inK reconstructed components) will be(33)CK-CR22=KM2N2NA2σT2=KMN-NANAMN-1∑l=K+1MNAl2.The noise of unreconstructed components can easily be related to the energy of the unreconstructed components(34)CK-C22=∑l=K+1MNAl2.That is, the total error in the reconstructed components is(35)CK-CR22=KMN-NANAMN-1CK-C22.This completes the proof of the theorem.


## 4.1. Initial Estimate

The initial (norm-two based) 2D-DCT estimation uses the available pixels only(10)C0p,q=∑m,n∈NAsm,nφMm,pφNn,q,where p=0,1,…,M-1,  q=0,1,…,N-1. The same results are obtained if the missing (unavailable) pixels assume zero values [7]. In a matrix form we can write(11)C0=ATy.The coefficients in (10) act as random variables, with different statistical properties at positions of the image components, (p,q)=(pl,ql), and positions not corresponding to image components, (p,q)≠(pl,ql).


## 4.2. Noise-Only Coefficients in Monocomponent Signals

We will first observe the monocomponent signal case, that is, whenK=1, and then generalize the result for multicomponent signals. Without loss of generality, we will assume that the amplitude is A1=1. From (5) and (10) we get (12)C0p,q=∑m,n∈NAφMm,p1φNn,q1φMm,pφNn,q.The variable(13)xp1q1m,n,p,q=φMm,p1φNn,q1φMm,pφNn,qis random for random values of (m,n). Its statistical properties for (p,q)≠(p1,q1) are studied next. Special cases are considered in Appendix. The initial 2D-DCT estimate can be written in the form(14)C0p,q=∑m,n∈NAxp1q1m,n,p,q.When(p,q)≠(p1,q1), the 2D-DCT coefficients correspond to nonsignal (noise) position and C0(p,q) behaves as a random Gaussian variable [7]. Using the basis functions orthogonality(15)∑m=0M-1∑n=0N-1xp1q1m,n,p,q=δp-p1,q-q1and the fact that values of xp1q1(m,n,p,q) are equally distributed, it can be concluded that the mean-value of C0(p,q) is equal to zero:(16)μC0p,q=EC0p,q=0,p,q≠p1,q1.In the case of the coefficient corresponding to the image component, using the same orthogonality property and the assumption of equal distribution of valuesxp1q1(m,n,p,q), it follows that(17)μC0p,q=EC0p,q=NAMN,p,q=p1,q1.For the zero-mean random variable, the variance definition is(18)σC0p,q2=E∑m,n∈NAxp1q12m,n,p,q+∑m,n∈NA∑i,j∈NAi,j≠m,nxp1q1m,n,p,qxp1q1i,j,p,q.As in the case when(p,q)≠(p1,q1) is observed, it can be concluded that(19)∑m=0M-1∑n=0N-1xp1q1m,n,p,q=0.Multiplying the left and right side of (19) by xp1q1(i,j,p,q) and taking the expectation of both sides we get(20)E∑m=0M-1∑n=0N-1xp1q1m,n,p,qxp1q1i,j,p,q=0,with (i,j)∈N. Values xp1q1(m,n,p,q) are equally distributed. Therefore, terms Exp1q1m,n,p,qxp1q1i,j,p,q for (m,n)≠(i,j) are the same and equal to a constant D. The total number of these terms is MN-1. Further, based on (20) we get(21)MN-1D+Exp1q12m,n,p,q=0.The initial variance definition can be written as(22)σC0p,q2=NAExp1q12m,n,p,q+NA2-NAD,as there are exactly NA expectations with quadratic terms in the first summation and NA(NA-1) terms in the second variance summation equal to D. In order to determine the unknown term Exp1q12(m,n,p,q), several special cases should be taken into account. Special cases of the 2D-DCT indices are considered in Appendix.Consider the general case whenp≠p1,  p≠M-p1,  q≠q1,  q≠N-q1 are satisfied. Then(23)Exp1q12m,n,p,q=EφM2m,p1φN2n,q1×EφM2m,pφN2n,q=1M2N2holds. Incorporating this result into (21) we get that (24)D=-1M2N21MN-1.Further, based on (22) the variance can be written as(25)σC0p,q2=NAMN-NAM2N2MN-1.This result also holds when (p1,q1) = (0,0). Note that when A1≠1, the result is multiplied by A12.It can be easily concluded that the average value of the variance (A.12) when all special cases from Appendix are included is constant and equal to(26)σ¯C02=A12NAMN-NAM2N2MN-12MN-214.As MN≫1, an accurate approximation for the average variance of noise-only coefficients follows(27)σN2=σ¯C02≈A12NAMN-NAM2N2MN-1.


## 4.3. Noise-Only Coefficients in Multicomponent Signals

In the multicomponent signal case, the observed random variable becomes(28)C0p,q=∑m,n∈NA∑l=1KAlφMm,plφNn,ql×φMm,pφNn,q.In this case, the coefficients at noise-only positions(p,q)≠(pl,ql) are random variables Gaussian in nature and zero-mean, as they are formed as the summation of independent zero-mean Gaussian variables over l. Namely, now the missing pixels in each image component contribute to the noise, and the noise originating from each component is proportional to the squared amplitude of that component, following (27) with Al,l=1,…,K. Therefore, 2D-DCT coefficients mean-value for a multicomponent signal (image) can be written as(29)μC0p,q=NAMN∑l=1KAlδp-pl,q-ql.The average variance of noise-only coefficients in this case easily follows(30)σ¯C02=∑l=1KAl2NAMN-NAM2N2MN-1.However, it is important to mention that components of the image multiplied with basis functions may cause a coupling effect if they are placed at positions satisfying certain conditions. Consequently, this effect may cause the increase of the previously derived variance at these positions. However, if it appears, for example, at the position(p1,q1) then the variance will be decreased for the same amount at the position (M-p1,N-q1). Therefore, we can further neglect this effect and assume that the variance expression in (30) holds in mean, which is crucial for the following derivation of the error in the nonsparse image reconstruction.


## 4.4. Nonsparse Signal Reconstruction

We consider that an image is reconstructed under the assumption that it isK-sparse and that it satisfies the condition for unique reconstruction in the compressive sensing theory. The number of reconstructed components is K. According to (30), each unreconstructed component in the image behaves as a Gaussian input noise with variance(31)σN2=Al2NAMN-NAM2N2MN-1.Therefore, allMN-K unreconstructed components will behave as a noise with variance(32)σT2=∑l=K+1MNAl2NAMN-NAM2N2MN-1.After reconstruction, the total noise energy from the unreconstructed components (inK reconstructed components) will be(33)CK-CR22=KM2N2NA2σT2=KMN-NANAMN-1∑l=K+1MNAl2.The noise of unreconstructed components can easily be related to the energy of the unreconstructed components(34)CK-C22=∑l=K+1MNAl2.That is, the total error in the reconstructed components is(35)CK-CR22=KMN-NANAMN-1CK-C22.This completes the proof of the theorem.


## 5. Numerical Results

In this section, the theoretical result from (35) is numerically checked on a number of test images. The images are used for the numerical calculation of the expected squared error with various sparsity K per block. The block size is assumed to be B×B. The squared errors in one block are calculated as(36)Estat=10log⁡CK-CR22to obtain the numerical result, whereas the theoretical curves are calculated using the right side of (35), that is,(37)Etheor=10log⁡KB2-NANAB2-1CK-C22.These errors are calculated for each block separately and then the results are averaged over all blocks in an image. The statistical peak signal-to-noise ratio (PSNRstat) is defined as(38)PSNRstat=10log⁡2552CK-CR22and the theoretical one is calculated according to(39)PSNRteor=10log⁡2552KB2-NA/NAB2-1CK-C22,where 255 is considered as the maximal pixel value of an image. They are used to additionally validate the results. In all following examples the reconstruction is performed using the OMP algorithm.Example 1.
The considered image is the grayscale image “Barbara” of size512×512. The image is first split into blocks B × B = 16 × 16. It is assumed that 60% of pixels are available. In the reconstruction, the sparsity is assumed to be K=16 per each block. The original image is shown in Figure 1(a), the image with the available pixels is shown in Figure 1(b), and the reconstructed image from reduced set of pixels, with assumed sparsity, is shown in Figure 1(c).
The statistical error and the theoretical one are shown in Figure2. We considered various sparsity levels K per each block, changing between 1 and 16. The red asterisk represents the statistical values and the theoretical result is presented with the black line.Figure 1
Reconstruction of image “Barbara” with60% available pixels and sparsity K=16 per each block of size 16×16: original image (a); noisy image (b); reconstructed image (c).
(a)
(b)
(c)Figure 2
Error caused by the unreconstructed components with various sparsity per block in image “Barbara”; red asterisk: statistics, black line: theory.Example 2.
Let us consider the RGB image “Lena” of size512×512. We will again split the image into blocks of size B×B=16×16. It is assumed that 60% of pixels are available. The sparsity is assumed to be K=16 per each block. The original image, image with the available pixels, and the reconstructed image are shown in Figure 3.
The statistical error and the theoretical one are shown in Figure4. The results are obtained by averaging errors from each block and each channel. Sparsity K per each block was varied between 1 and 16. The red asterisk represents the statistical values and the black line represents the theoretical result.Figure 3
Reconstruction of image “Lena” with60% available pixels and sparsity K=16 per each block of size 16×16: original image (a); noisy image (b); reconstructed image (c).
(a)
(b)
(c)Figure 4
Error caused by the unreconstructed components with various sparsity per block in image “Lena”; red asterisk: statistics, black line: theory.Example 3.
A test image set with standard MATLAB images, shown in Figure5, is used for this example. Each image is split into B×B=16×16 blocks. The reconstruction is performed under the sparsity assumption K=16, with 60% of randomly positioned available pixels. The statistical and the theoretical errors are calculated according to (36) and (37), whereas the PSNR is calculated using (38) and (39). The results are presented in Table 1, confirming a high agreement between the theory and statistics.Table 1
Error and PSNR for 8 test images.
Test image
Error
PSNR
Statistics
Theory
Statistics
Theory
Boat
−19.13
−19.20
81.97
82.13
Pout
−27.32
−27.38
80.35
80.42
Pirate
−10.10
−10.23
70.97
71.10
Lifting Body
−24.78
−24.86
82.97
83.11
Pears
−25.60
−25.67
78.77
78.86
Autumn
−15.80
−15.88
90.81
90.92
Peppers
−22.16
−22.22
79.16
79.23
Football
−18.72
−18.87
68.69
68.83Figure 5
The test image set used for the analysis in Example3.


## 6. Conclusions

In this paper, we considered the influence of nonsparsity in the reconstruction of images. Images are originally sparse or approximately sparse in the two-dimensional discrete cosine transform domain. The reconstruction error relation is presented in the form of a theorem. The reconstruction results are checked on a number of images, both grayscale and color. It is confirmed that the statistical results are close to the derived theoretical results.



---

*Source: 4314527-2018-02-12.xml*