Sparse coding, a method that decomposes a signal into a few elements of a dictionary, can uncover semantic information about images^[1] and has been applied in image processing tasks such as image inpainting^[2] and feature extraction^[3−5]. Image inpainting can fill in missing parts of an image and is commonly used to repair aged photos and damaged image files. Feature extraction can reduce the dimensionality of the signal, obtain essential features, and improve the efficiency of data processing. The forward stagewise regression (FSR) is one of the promising algorithms to solve the sparse coding problem and provides competitive results with the commonly used lasso algorithm^[6−8]. However, FSR usually involves massive dot product operations to compute the cosine distance, which severely limits the efficiency of the FSR algorithm. Nevertheless, in 2015, RJ. Tibshirani proposed that FSR will outperform the lasso in efficiency when implemented in a highly parallel computing paradigm^[7]. Then, for the first time, this work discusses the adoption of memristive systems to accelerate FSR and perform sparse coding. The memristive in-memory computing (IMC) paradigm is an appealing parallel computing approach to perform dot product operations with O(1) time complexity^[9−12]. And the IMC has been widely explored to accelerate the processing of applications like the neural network^[13], signal process^[14], and regression^[15]. Recently, sparse coding has also been implemented on the memristor arrays with encouraging performance improvement compared with conventional CMOS-based systems^[16−19].

However, these memristive sparse coding systems are chosen to be as efficient as possible, regardless of the degradation of the dictionary and the corresponding detrimental effects on image reconstruction and feature extraction. In their system, a locally competitive algorithm is chosen for implementation. Then, to reduce the time complexity of the algorithm, both the forward and backward iterative operations of the algorithm are accelerated by analog operations. Next, the encoding results will be solely based on the dictionary held on the memristor array. However, the accuracy and reliability of the dictionary are not guaranteed. When the dictionary is stored on the memristor array, it deteriorates into various dictionaries at different terminals due to the accuracy and variability of the memristor^[16]. After that, the image cannot be reconstructed by a deterministic dictionary. Ultimately, this inevitably harms image reconstruction and affects the associated image feature extraction^[18]. To solve this problem, some computations need to be performed by a digital system to control the accuracy of the algorithm. However, the time complexity of the forward and backward iteration steps of the local competition algorithm is similar, and speeding up only one step does not reduce the time complexity of the entire algorithm. Therefore, to ensure accuracy while speeding up the execution of sparse coding, memristive systems should consider digital-analog hybrid operations and alternative algorithm.

In this work, to ensure the quality of sparse coding while accelerating it, we propose a digital-analog hybrid memristive sparse coding system (Fig. 1). In this system, the sparse coding is implemented by forward stagewise regression with mixed digital-analog operations. During the process, an approximate dictionary is mapped to the memristor array to speed up the calculation of the cosine distance between the dictionary elements and the residual vectors, while a full-precision dictionary is stored in the digital system to precisely update the reconstructed image. Thus, by implementing the calculation of the cosine distance on the memristor array, the computational time complexity of FSR can be reduced from O(m × n) to O(m + n). Besides, the reconstruction is conducted based on the dictionary stored in the digital system, which avoids the dictionary being deteriorated by the nonidealities of the devices. Additionally, to reduce the precision required on the digital-to-analog converters (DACs), a dynamically adjusted data mapping method is proposed. Finally, in the image inpainting task, which is an important application of sparse coding, the proposed method can provide accurate reconstruction on a natural image with 50% lost pixels.

The procedure of sparse coding involves dictionary construction and sparse representation. The constructed dictionary can be either the predefined dictionary or the learned dictionary. The FSR algorithm is utilized for achieving sparse representation. In this section, we illustrate the principle of accelerating the FSR algorithm by memristive IMC. Initially, we introduce the multilevel Pt/Al₂O₃/AlO_x/W memristor, followed by the algorithm of the FSR. The evaluation of the memristor-based FSR is predicated on the performance of the aforementioned multilevel memristors. We then propose data mapping methods and finally demonstrate the digital-analog hybrid system.

We fabricated a Pt/Al₂O₃/AlO_x/W stacked memristor. After depositing a Ti adhesion layer on the Si/SiO₂ substrate, we deposited a 100-nm Pt bottom electrode by direct current (dc) magnetron sputtering. Then, through the process of atomic layer deposition, a 3-nm Al₂O₃ layer was formed, followed by a 5-nm AlO_x layer which was deposited via radio frequency magnetron sputtering. Finally, the 100-nm W top electrode was grown by dc magnetron sputtering and patterned by ultraviolet lithography with a size of 50 × 50 μm². A sketch of the device structure is given in Fig. 2(a). Fig. 2(b) shows the scanning electron microscope (SEM) image of the devices. As shown in Fig. 2(c), based on the Al 2p and O 1s X-ray photoelectron spectroscopy (XPS) images in Al₂O₃ and AlO_x layers, it can be observed that the O 1s peak in the AlO_x layer exhibits a higher shift in binding energy at 531.10 eV compared to the Al₂O₃ layer, which indicates the higher oxygen vacancy concentration in the AlO_x layer. Homogeneous bilayer structure with oxygen vacancy concentration gradients results in a stable resistive switching behavior of the device. Fig. 2(d) exhibits the 100 consecutive dc I−V curves of the Pt/Al₂O₃/AlO_x/W memristor. High-resistance-state (HRS) and low-resistance-state (LRS) distributions of 10 devices are highly consistent, as shown in Fig. 2(e). Compared to analogous reported devices, our device has achieved multi-conductance states modulation appropriate for sparse encoding by using the write-verify operation method^{[20, 21]}. A case of tuning the device to a target conductance state of 60 μS by the write-verify method is shown in Fig. 2(f). The tiny step voltage (±20 mV) adopted in the write-verify scheme guarantees high accuracy of conductance modulation. Fig. 2(g) displays the modulation results of the eight high conductance states (HCSs) of the devices, while maintaining variations below 3%. The read distribution of eight target conductance states is illustrated in Fig. 2(h), which is desirable for the sparse coding model. Fig. 2(i) demonstrates over 3000 s retention results of eight HCSs proving the reliability of the Pt/Al₂O₃/AlO_x/W memristor.

FSR serves as a kind of L1 norm regression is widely used in processing sparse models^[6−8]. In the regression, the n-dimension output vector y can be represented by the n-dimension variable vectors x₁, x₂,···, x_m as in the following:

1y=β1x1+β2x2+⋯+βmxm,

where β stands for the coefficient estimates of variables x₁, x₂,···, x_m. To model y as a linear combination of x₁, x₂,···, x_m, the FSR updates the coefficient estimates β^(k) by calculating the cosine distance to find the most relevant variable with the current residual y−ŷ, and then transfer the newly estimated ŷ to the next iteration. For the k_th iteration, the processes can be expressed as follows:

2j=argmaxj=1,⋯,m{|xjT(y−y^)|},

3βj(k+1)=βj(k)+ε⋅sign{xjT(y−y^)},

4y^+=ε⋅sign{xjT(y−y^)}⋅xj,

where j stands for the index of the most related variable, and ε is the step size. Such iteration continues until the repeat time k reaches the set maximum or the fitting error ║y−ŷ║₂ converges under a certain level. After the convergence, the stagewise estimate will follow the desired sparsity properties^[22]:

5‖β(k)‖1⩽kεand‖β(k)‖0⩽k.

The flow chart of the FSR is illustrated in Fig. 3(a), where the calculation of cosine distance dominates in the whole process of the algorithm with the computational complexity of O(m × n). Therefore, by performing this step on the memristor array in an O(1) manner, the complexity of the FSR could be reduced to O(m + n). At the same time, the computational accuracy of the algorithm can be controlled by the parameter iteration operations performed in the digital system. Theoretically, the execution of the FSR can be accelerated by low-precision memristive calculations while ensuring computational accuracy.

For the implementation of FSR on the memristor arrays, the variables x₁, x₂,···, x_m and the residual vector y−ŷ are mapped as the device conductance and the input voltages, respectively. However, the dilemma of data mapping is that the precision of the data is usually above 8 bits, while the number of available memristor conductance states and the precision of the DAC are usually limited. To reduce the precision requirements of the in-memory sparse coding for conductance and voltage, two optimized data-mapping methods are proposed for the variables and residual vectors, respectively. For the variables, (1) standardize the data separately for each variable vector (z-score standardization)^[23], (2) all values are mapped according to the designed precision and the truncation range, and (3) the difference between the two memristors is used to represent the mapped values. For the residual vector, the values of the vector shrink as the regression plane fits the data better through the iterations. Therefore, it is difficult to map the residual vectors to voltages continuously and adequately with a fixed numerical-voltage mapping ratio and low-precision DACs. Accordingly, we propose a dynamically adjusted mapping method (Fig. 3(c)): (1) calculate the average absolute value of the vector elements, (2) take some equally spaced points around 0 to map all the values in the vicinity, where the spacing is dependent on the previously calculated average value, and (3) use the DACs to convert the mapped values into voltages. Moreover, to reduce the computing burden of the digital system, the average value could be updated every few iterations, since it does not vary significantly.

We note that the above mapping method may lead to severe truncation errors at several data points, because it does not use the maximum value as the upper limit of the mapping range. However, large truncation errors occur mainly for outliers, which are usually detrimental to regression analysis^[24]. Additionally, the calculation of cosine distances requires only relative values to find the most relevant variables, which can tolerate the mapping error to a certain extent.

Here, we illustrate the operation process of the proposed hybrid digital-analog system. After the variables x₁, x₂,···, x_m are stored on the memristor array in an approximate map-ping manner, the system initializes the regression coefficients β⁽⁰⁾ and predicted values ŷ to zero and then starts iteration. During the iteration process, first, the residual vector y−ŷ is converted into a voltage vector according to the aforementioned method and applied to the array. Then, the outputs of the circuit are sampled by analog-digital converters (ADCs), and the results are the approximate cosine distances of the residual vector y−ŷ and variables x₁, x₂,···, x_m, which can be used to find the most relevant variable to the current residual vector (Fig. 3(b)). Next, the regression coefficient of this variable is updated by adding ±ε (the sign depends on the cosine similarity), and the predicted value ŷ is updated with that variable in the digital part with full precision. Finally, the updated ŷ is transferred to the next iteration. Once the number of iterations reaches the upper limit or the fitting error ║y−ŷ║₂ reaches below the threshold, it outputs the regression coefficients β^(k), completing the variable selection and sparse estimations. In the above procedure, the cosine similarity is computed based on Ohm's law and Kirchhoff's law in the analog circuit, and the parameter iteration operation is based on full-precision computation in the digital system. While low-precision analog circuits are used to perform the most costly computations, full-precision digital operations ensure the computational accuracy of the algorithm. This system takes full advantage of digital-analog hybrid operation and reflects the adaptability of the FSR.

In this section, we demonstrate the use of memristor-based FSR to solve sparse coding tasks. During the process, the variable matrix X is the dictionary, the real value y is the image patch, and the fitting goal is to fit the image patch with the dictionary elements. We will first introduce the algorithm for sparse coding and then perform simulations to verify that the memristor-based FSR can accurately handle sparse coding tasks. The key step, calculating the cosine distance between the residual vector and dictionary elements, is implemented in a modeled memristor array, where the analog properties are simulated on the python platform. Additionally, considering that both the predefined and learned dictionaries are widely used, we employ both dictionaries to perform memristor-based sparse coding and compared the results.

Sparse coding algorithms aim to find a linear combination of a small number of dictionary elements to represent the input signal. It can reduce the dimensionality of high-dimensional data, find essential features of signals, and extract semantic information of graphs. As such, it has a broad range of applications in computer vision and signal processing. Sparse coding usually contains two steps, namely, the construction of a dictionary and the sparse representation. Predefined dictionaries (DCT, Gabor) and learned dictionaries are widely used in this field^[5]. The predefined dictionaries can be obtained by sampling the wave^{[25, 26]}, while the learned dictionary can be obtained by dictionary learning algorithms such as K-SVD^[2]. After the dictionary is obtained, the mathematical description of sparse representation can be viewed as an L0-norm minimization^[16]:

6min{∑i=1n(yi−∑j=1mxijβj)2}subjectto‖β‖0⩽q,

where y is the image patch, X is the dictionary, β is the coefficient estimation of the dictionary elements, and q is the number of selected elements. However, since the L0-norm minimization is an NP-hard problem, the L1-norm minimization is a popular choice to replace it in sparse coding, as these two methods have the same effect when the solution is sparse enough^[27]. Sparse representation algorithms include lasso, orthogonal matching pursuit, forward stagewise regression, local competition algorithm, etc. Consider the excellent performance of forward stagewise regression and its adaptability to digital-analog hybrid operations. The goal of this work is to use digital-analog hybrid operations to accelerate the execution of forward stagewise regression while ensuring computational accuracy.

​Here we will evaluate the sparse representation performance of the memristor-based FSR with the DCT dictionary and learned dictionary. The over-determined DCT dictionary can be obtained by sampling the cosine wave at different frequencies^[25]. The scale of the dictionary is 64 × 256, which contains 256 image features, with each feature consisting of 64 weights. Limited by the finite conductance states of the memristor, the precision of the dictionary is reduced to 4-bit, and then is mapped as the difference between two memristor arrays. The multiple conductance states in the device model were set to 60, 80, 100, 120, 140, 160, 180, and 200 μS with 4% (σ/μ)_write (write variation) and 4% (σ/μ)_read (read variation). The distribution of the conductance is shown in Figs. 4(a) and 4(b). Then, Figs. 4(c) and 4(d) demonstrate an example of memristor-based sparse coding, where the step size σ is set to 0.025, and the iteration number is 100. During the process, the number of selected dictionary elements increases with iterations (Fig. 4(e)), which is a forward selection method that allows us to obtain the most important features at the early stage^[28]. Finally, all patches will be sparse coding, and the entire image is reconstructed as in Fig. 4(f), showing good image reconstruction quality.

In Figs. 4(g) and 4(h), the sparse coding effects of the memristor-based FSR and the full-precision FSR at different thresholds are compared. The DAC precision is set to 4-bit. Then, at the expense of a little sparsity of selected elements, memristor-based FSR can achieve the same image reconstruction quality as the full-precision one. Furthermore, the image re-construction quality is inversely proportional to the number of selected dictionary elements, and the best image reconstruction quality surpasses that of prior studies^[16−19]. This suggests that memristor-based FSR can perform sparse coding with high efficiency and higher quality, and the DCT dictionary can be used for memristor-based sparse coding.

The learned dictionary is obtained by a dictionary learning algorithm trained on natural images. Here, the 64 × 256 DCT dictionary is selected as the initial dictionary and the K-SVD algorithm^[2] is used to learn a dictionary offline without considering the hardware nonidealities. The training set is shown in Fig. 5(a), which does not contain the testing image. Then the offline-learned dictionary is obtained as shown in Figs. 5(b) and 5(c), which has been mapped onto the memristor devices the same as that of the DCT dictionary. To compare the performance of memristor-based FSR using the two dictionaries, the same thresholds are taken to perform sparse coding on the offline-learned dictionary. Then, compared with the DCT dictionary, the offline-learned dictionary achieves a higher upper limit of image reconstruction quality and better sparsity (Figs. 5(d) and 5(e)). This suggests that existing learned dictionaries can be directly mapped to memristor arrays to accelerate sparse coding and achieve better results than when using DCT dictionaries.

To analyze the influence of the various hardware nonidealities on the system, we further conduct simulation analysis. The offline-learned dictionary is selected for the analysis according to the image reconstruction quality, and the threshold is set as in the condition when the reconstruction error (mean square error) is less than 0.0006 to balance the reconstruction quality and sparsity. As can be seen in Fig. 6(a), the 4-bit conductance is sufficient for the sparse coding tasks compared to the higher-precision ones, and 3-bit conductance is also tolerable only when the number of selected elements increases by 6%. This means that memristors with only four states (equivalently 3-bit for differential pairs) can be used to perform sparse coding for natural images, while prior studies usually required over eight states^[16−19]. In Fig. 6(b), with 4-bit precision DACs, this system can achieve similar reconstruction quality as that of the full precision ones (Fig. 5(e)). Higher precisions can further improve the result, but such improvement is not significant considering the heavy hardware burden of high-precision DACs. Then, under the condition that the voltages and conductance are both 4-bit precision, after a 64-bit MAC operation, the output results should be sampled by 14-bit ADCs to maintain full precisions. However, Fig. 6(c) shows that 10-bit ADCs are enough for this task, because the differences of the conductance obey a normal distribution and the absolute values of the voltage vectors are usually low. Finally, the robustness of this system under various device variations is analyzed. As shown in Fig. 6(d), even with 30% (σ/μ)_write and 30% (σ/μ)_read, our system still achieves the same image reconstruction quality with the ideal result. But in Fig. 6(e), the sparsity drops faster, tolerating only 15% (σ/μ)_write and 15% (σ/μ)_read with the number of selected elements increased by 15%.

The purpose of image inpainting is to restore corrupted images, and it is commonly used to repair aged photos or image files that have been corrupted during data transfer. Sparse coding can capture semantic information from the remaining pixels of a corrupted image to fill in the missing parts. With the above hardware parameter design considerations, to demonstrate that the memristor-based FSR can be applied to a realistic image processing task, we apply it to complete image inpainting (a basic application of sparse coding^[29]). Here, we randomly delete 50% of the pixels in the image and then applied memristor-based FSR to restore their values with the DCT dictionary and the learned dictionary, respectively. In the process, the damaged picture was first split into 8 × 8 patches. Then, in the loop iteration stage, the similarity between the residual vector y-ŷ and the dictionary elements are computed and the coefficient of the most relevant dictionary element is updated. Moreover, the image inpainting task only computes the similarity between the residual vectors of the remaining pixels and the dictionary elements (Fig. 7(a)), while sparse coding typically computes the similarity between the residual vectors of all pixels and the dictionary elements. After a certain number of loop iterations, the image is reconstructed based on the coefficients of the dictionary elements to obtain an image filled with missing pixels. Finally, the learned dictionary achieves better image reconstruction than the DCT dictionary (Fig. 7(b)), with a reconstruction error of 0.0424 root-mean-squared error (RMSE). This indicates that the memristor-based FSR can perform the task of image inpainting.

Finally, we now compare our study with similar works reported in the literature. Can et al. have developed a 128 × 64 memristor array for signal and image processing tasks^[14]. This in-memory computing system exhibits a significantly higher energy efficiency of 119.7 TOPS/W compared to von Neumann-based chip architectures, highlighting the notable advantages of memristor-based in-memory computing systems in enhancing the efficiency of the image-processing algorithm. Sheridan et al. experimentally implemented a memristor-based locally competitive algorithm (LCA) for sparse coding, which theoretically can achieve 16 × improvement in power consumption than the digit CMOS system^[16]. Woods et al. provided an LCA-like algorithm using a spiking framework, which resulted in a more energy-efficient sparse coding architecture, improving an all-CMOS ASIC with 21 × the throughput while using 99% less energy per input^[18]. These systems fully demonstrate that IMC can achieve a sufficiently high energy efficiency at the data scale for sparse coding applications. This work does not outperform them in terms of energy efficiency. But we solved a common problem with their memristive sparse coding systems, the dictionary quality degrades on the memristor array, and images cannot be reconstructed with a definite dictionary. In their systems, the memristor array is employed to store the dictionary. But the variations of the memristor, which may be caused by the various device characteristics and fabrication procedures, will deteriorate one dictionary to various dictionaries in different terminals. Then the above-mentioned problem will arise and critically harm the image reconstruction, which is considered to affect image feature extraction^[18]. In contrast, in this work, the memristor array is just used to approximately calculate the cosine distance between the dictionary elements and the residual vector. And the encoding results of different terminals are based on a full-precision dictionary in the digital system, which is not affected by the nonidealities of the devices. Therefore, this memristor-based system can achieve higher image reconstruction quality than the previous studies (Table 1). Specifically, the proposed system achieves the highest image reconstruction quality among memristive sparse coding systems with the same compression ratio (L0/patch size). It is worth noting that this is the first time a low-precision memristive sparse coding system has achieved an image reconstruction quality of 38 dB.

In this work, we introduced a digital-analog hybrid memristive sparse coding system (memristor-based FSR), which can reduce the time complexity of the FSR from O(m × n) to O(m + n) by utilizing memristive IMC. Besides, the image reconstruction quality (PSNR) of memristive sparse coding can be improved to 38 dB. The hardware requirements of the system are low, which only requires moderate memristor conductance states (≥ 4), write variation (≤ 15%), read variation (≤ 15%) and DACs (≥ 4 bits). In the image inpainting task, this method has restored the image with 50% lost pixels, and the reconstruction error after a filling is 0.0424 RMSE. These results show that memristor-based FSR can accomplish sparse coding with high efficiency and high quality, and is promising for applications such as image recognition, anomaly detection, etc.