IEEE Circuits and Systems Magazine - Q1 2018 - 40

The major challenge of customizing power iteration for memristor
implementation is to determine the multiplicity of the dominant
eigenvalue and to find the corresponding eigenvectors.
pursuit (OMP) algorithm [77], a commonly used software-based CS solver. We observe that the recovery accuracy improves as the signal becomes sparser, namely,
s is smaller. This is not surprising, since a sparser signal
can be more stably recovered at the rate much smaller
than what is commonly prescribed by Shannon-Nyquist
theorem [70]. By fixing s, we observe that the recovery
accuracy decreases while increasing the level of hardware variations. Although the presence of hardware
variations negatively affects the recovery accuracy,
the sparse pattern error shown by Figs. 8(b) and (c) is
acceptable, as it is below 6%. In particular, in Fig. 8(c) the
recovered signal yields almost the same sparse support
as that of the original signal even in the presence of 10%
hardware variation. These promising results show that
the memristor-based CS solver is quite robust to hardware variations, and is able to provide reliable recovered
sparse patterns. Lastly, we investigate the convergence
of the memristor-based approach against different
values of the ADMM parameter t. Similar to Fig. 7, a
moderate choice of t, namely, t = 10 in this example, is
preferred over others as shown in Fig. 8(d).
VI. Power Iteration via Memristors:
Application to PCA
Principal component analysis (PCA) is the best-known
dimensionality-reduction technique to find intrinsic lowdimensional manifolds from high-dimensional data [40].
The implementation of PCA requires the computation of
the principal eigenvalues and the corresponding eigenvectors of a symmetric matrix. The calculation of eigenvalues and eigenvectors is also motivated by optimization problems, e.g., a projection onto semidefinite cones
in semidefinite programming [78]. Since power iteration
(PI) is a widely-used algorithm for eigenvalue analysis
[79], here we describe a memristor-based PI framework.
A. Preliminaries on PI
PI is an iterative algorithm that converges to the eigenvector associated with the largest eigenvalue of a matrix.
Let {(m i, u i)} in= 1 denote a set of eigenvalue-eigenvector
pairs for matrix A ! R n # n, where we refer to m 1, regardless of its multiplicity, as the dominant eigenvalue. The
kth iteration of PI is given by [42]
k -1

x k = Axk -1 ,
< Ax < 2
40

ieee circuits and systems magazine

where x 0 is an arbitrary starting vector. If k " 3, then
by (32), x k converges to the eigenvector u 1, and thus
(x k) T Ax k / (x k) T x k converges to the largest eigenvalue m 1 . The convergence of PI is geometric, with ratio
|m 2|/|m 1| [42]. Therefore, PI converges slowly if there is
an eigenvalue close in magnitude to the dominant eigenvalue. Moreover, if the largest eigenvalue is not unique,
say m 1 = m 2 with multiplicity 2, the limiting point x k fails
to converge to u 1, and instead converges to a linear
combination of eigenvectors u 1 and u 2 [80]. Thus, it is
required that the memristor-based PI be able to address
the issue of repeated eigenvalues.
B. Memristor-Based PI
It is clear from (32) that the PI algorithm involves a)
matrix-vector multiplication Ax k -1, and b) evaluation of
a vector norm. Based on (2), the first operation is easily
implemented using memristor crossbars. And the second
operation can be realized using elementary digital (or
analog) circuits [30]. The major challenge of customizing
PI for memristor implementation is to determine the multiplicity of the dominant eigenvalue and to find the corresponding eigenvectors. In what follows, we show that with
the aid of Gram-Schmidt process such a problem can be
addressed via elementary matrix-vector operations.
We assume that the largest eigenvalue has multiplicity s, namely, m 1 = m 2 = g = m s . Under s random initial
vectors, we denote by {y i} is= 1 the converging vectors of
PI. It is known from [80] that {y i} is= 1 are linear combinations of eigenvectors {u i} is= 1 . This implies two facts.
p
First, given p initial vectors, the resulting {y i} i = 1 are
linearly independent if p # s. Therefore, we are able
to determine the number of repeated dominant eigenvalues by adding new columns to Yp until its rank
stops increasing where Yp := [y 1, g, y p], and its rank
can be determined by the singularity of Yp Y Tp . Second,
given the number of repeated eigenvalues, finding the
eigenvectors {u i} is= 1 is equivalent to seeking an orthogonal subspace spanned by {y i} is= 1 . This procedure
is precisely described by the Gram-Schmidt process.
Given a sequence of vectors {y i} is= 1, the Gram-Schmidt
process generates a sequence of orthogonal vectors
{u i} is= 1 [42],
i -1

ui = yi - /

j =1

(32)

y Ti u j
u j, i = 2, g, s,
u Tj u j

(33)

where u 1 = y 1 .
first quarter 2018



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

Contents
IEEE Circuits and Systems Magazine - Q1 2018 - Cover1
IEEE Circuits and Systems Magazine - Q1 2018 - Cover2
IEEE Circuits and Systems Magazine - Q1 2018 - Contents
IEEE Circuits and Systems Magazine - Q1 2018 - 2
IEEE Circuits and Systems Magazine - Q1 2018 - 3
IEEE Circuits and Systems Magazine - Q1 2018 - 4
IEEE Circuits and Systems Magazine - Q1 2018 - 5
IEEE Circuits and Systems Magazine - Q1 2018 - 6
IEEE Circuits and Systems Magazine - Q1 2018 - 7
IEEE Circuits and Systems Magazine - Q1 2018 - 8
IEEE Circuits and Systems Magazine - Q1 2018 - 9
IEEE Circuits and Systems Magazine - Q1 2018 - 10
IEEE Circuits and Systems Magazine - Q1 2018 - 11
IEEE Circuits and Systems Magazine - Q1 2018 - 12
IEEE Circuits and Systems Magazine - Q1 2018 - 13
IEEE Circuits and Systems Magazine - Q1 2018 - 14
IEEE Circuits and Systems Magazine - Q1 2018 - 15
IEEE Circuits and Systems Magazine - Q1 2018 - 16
IEEE Circuits and Systems Magazine - Q1 2018 - 17
IEEE Circuits and Systems Magazine - Q1 2018 - 18
IEEE Circuits and Systems Magazine - Q1 2018 - 19
IEEE Circuits and Systems Magazine - Q1 2018 - 20
IEEE Circuits and Systems Magazine - Q1 2018 - 21
IEEE Circuits and Systems Magazine - Q1 2018 - 22
IEEE Circuits and Systems Magazine - Q1 2018 - 23
IEEE Circuits and Systems Magazine - Q1 2018 - 24
IEEE Circuits and Systems Magazine - Q1 2018 - 25
IEEE Circuits and Systems Magazine - Q1 2018 - 26
IEEE Circuits and Systems Magazine - Q1 2018 - 27
IEEE Circuits and Systems Magazine - Q1 2018 - 28
IEEE Circuits and Systems Magazine - Q1 2018 - 29
IEEE Circuits and Systems Magazine - Q1 2018 - 30
IEEE Circuits and Systems Magazine - Q1 2018 - 31
IEEE Circuits and Systems Magazine - Q1 2018 - 32
IEEE Circuits and Systems Magazine - Q1 2018 - 33
IEEE Circuits and Systems Magazine - Q1 2018 - 34
IEEE Circuits and Systems Magazine - Q1 2018 - 35
IEEE Circuits and Systems Magazine - Q1 2018 - 36
IEEE Circuits and Systems Magazine - Q1 2018 - 37
IEEE Circuits and Systems Magazine - Q1 2018 - 38
IEEE Circuits and Systems Magazine - Q1 2018 - 39
IEEE Circuits and Systems Magazine - Q1 2018 - 40
IEEE Circuits and Systems Magazine - Q1 2018 - 41
IEEE Circuits and Systems Magazine - Q1 2018 - 42
IEEE Circuits and Systems Magazine - Q1 2018 - 43
IEEE Circuits and Systems Magazine - Q1 2018 - 44
IEEE Circuits and Systems Magazine - Q1 2018 - Cover3
IEEE Circuits and Systems Magazine - Q1 2018 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021Q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q1
https://www.nxtbookmedia.com