IEEE Circuits and Systems Magazine - Q1 2018 - 41

VII. Conclusion and Future Directions
In this paper, we presented an overview of a memristor-based optimization/computation framework that
exploits both memristors' properties and algorithms'
structures. Popularly used algorithms, ADMM and PI,
were selected to illustrate memristor crossbar-based
implementations. We showed that ADMM is able to decompose a complex problem into matrix-vector multiplications and subproblems for solving systems of linear
equations, which then facilitates memristor-based comfirst quarter 2018

Error: |λ-λ*|
Success
Rate (%)
Number of
Iterations (log2)

× 10-7

2
0

100
50
0

14
12
10
8
6

1 2
3 4
5
6 7
8
9 10
Multiplicity Time of Dominanat Eigenvalue

Figure 9. performance of the proposed pi solver against
the multiplicity of the dominant eigenvalue.

1.5

Memristor-Based
Approach

1.5

MATLAB pca Func.

1
PC2, Variance 5.31

C. Performance Evaluation
In what follows, we demonstrate the empirical performance of the proposed PI method to compute the dominant eigenvalues/eigenvectors based on a synthetic
dataset and to perform PCA based on the Iris flower
dataset [81]. To specify the eigenvalue problem, let A
be a symmetric matrix of dimension n = 50. We assume
that the dominant eigenvalue is repeated k times, where
k ! [1, 10] . The proposed algorithm continues until a
10 -4 -accuracy solution is achieved. Such an experiment
is performed over 50 independent trials. In Fig. 9, we present the computation error, success rate, and the number
of iterations of PI against the multiplicity of the dominant eigenvalue. Here the computation error is averaged
over 50 trials, and given by the difference between the
memristor-based solution m and the optimal solution m *
obtained from the eigenvalue decomposition. As we can
see, the proposed PI solver is of high accuracy with error
less than 10 -6 . Moreover, at each trial, the proposed solver correctly recognizes the number of repeated dominant
eigenvalues. And it converges fast, within 1000 iterations.
In Fig. 10, we apply the proposed PI solver to find the
principal components (PCs) of the Iris flower dataset,
which contains 150 iris flowers, and each flower involves
4 measurements, sepal length, sepal width, petal length
and petal width. These flowers belong to three different
species: setosa, versicolor, and virginica. We compare
the memristor-based approach with the standard pca
function in MATLAB. As we can see, both methods yield
the same 2 D data distribution and the same variance
of each PC. These results imply that the application of
memristor crossbars is of feasible for this problem.

PC2, Variance 5.31

By incorporating the Gram-Schmidt process (33),
the generalized PI algorithm is able to calculate the
dominant eigenvalue even if it is not unique. Once the
dominant eigenvalue m 1 is found, the second largest
eigenvalue m 2 can then be found by performing PI to
a new matrix A - m 1 u 1 u T1 , known as a matrix deflation
[42]. Since both (32) and (33) only involve elementary
matrix-vector operations, it is possible to accelerate PI
by using memristors.

0.5
0
-0.5

0.5
0
-0.5
-1

-1
-1.5
-4 -2 0
2
4
PC1, Variance 92.46
(a)
Setosa

-1.5
-4 -2 0
2
4
PC1, Variance 92.46
(b)

Versicolor

Virginica

Figure 10. pca results for the iris flower dataset. (a) memristor-based approach; (b) matLaB pca function.

puting architectures. To solve the eigenvalue problem
using memristor crossbars, we presented a generalized
version of the PI algorithm in the presence of repeated
dominant eigenvalues. The effectiveness of memristorbased framework was illustrated via examples involving
LP, QP, compressive sensing and PCA. The framework
showed a great deal of promise with low computational
complexity and high resiliency to hardware variations.
Although there has been a great deal of progress
on the design of memristor-based computation accelerators, many questions and challenges still remain to
ieee circuits and systems magazine

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2018