IEEE Circuits and Systems Magazine - Q1 2018 - 38
matrix, and v ! R q is a stochastic or deterministic error
with bounded energy ||v||2 # p.
The main goal of CS is to stably recover the unknown
sparse signal z * from noisy measurements h. It has
been shown in [75] that stable recovery can be achieved
in polynomial time by solving the convex optimization
problem for robust CS
minimize
||z||1
z
subject to ||Hz - h||2 # p,
(23)
where z ! R n is the optimization variable, and ||ยท||1 denotes the , 1 norm of a vector. In problem (23), the , 1
norm is introduced to promote the sparsity of z [70].
Note that problem (23) can also be formulated in the
form of LASSO or sparse coding [24], [67]
We recall from the standard form of ADMM given by (4)
T
that if we set x = 6z T , s T @ , y = 6w T , u T @, g ^ $ h = < $ < 1 + g l ^ $ h,
A = I, B =-I and c = 0 , then problem (4) reduces to the
CS problem (24). As a result, the ADMM step (6) with
respect to z and s can be written as
B. Memristor-Based Accelerator For Solving
CS Problems
Similar to memristor-based linear and quadratic optimization solvers, the key step to successfully applying
memristor crossbar arrays to CS problems is to extract
subproblems, with the aid of ADMM, that solve systems
of linear equations. By introducing three new optimization variables s ! R q, w ! R p and u ! R q, problem (23)
can be reformulated in a way that lends itself to the application of ADMM,
minimize f (z, s) +||w||1 + p (u)
subject to z - w = 0, s - u = 0,
(24)
where z, s, w and u are optimization variables, and f
and p are indicator functions corresponding to the constraints of problem (23), namely,
0 Hz - s = h
3 otherwise,
(25)
0 ||u||2 # p
3 otherwise.
(26)
f (z, s) = '
and
p (u) = '
In (24), the introduction of new variables s, w and u
together with the indicator functions (25)-(26) allows
us to split the original constrained problem into subproblems for solving systems of linear equations, and
elementary proximal operations related to the , 1 norm
and the Euclidean ball constraint [53].
38
ieee circuits and systems magazine
t
(27)
where a 1 := w k -(1/t) n 1k, a 2 := u k -(1/t) n k2, n =[n T1 , n T2 ] T
! R p +q is the vector of dual variables corresponding to
problem (24), and k is the ADMM iteration number. The
solution of problem (27) is given by KKT conditions:
tz + H T m = ta 1, ts - m = ta 2, and Hz - s = h, where
m ! R q is the Lagrangian multiplier corresponding to
problem (27). These form a system of linear equations
z
ta 1
tI p 0 H T
C > s H = >ta 2H, C = > 0 tI q -I qH .
m
h
H -I q 0
minimize
||Hz - h||22 + c ||z||1,
z
where c is a regularization parameter that governs the
tradeoff between the least square error and the sparsity
of z. In what follows, we focus on the problem formulation in (23).
t
< z - a 1 < 22 + < s - a 2 < 22
2
2
subject to Hz - s = h,
minimize
z, s
(28)
Based on (2), the linear system (28) can be mapped onto
a memristor network by configuring its memristance
values. Recall that a programmed memristor crossbar
only requires a constant-time complexity O(1) to solve
problem (28).
The ADMM step (8) with respect to w and u becomes
minimize
< w < 1 + p (u) +
w,u
t
2
< w - b 1 < 22 +
t
2
< u - b 2 < 22, (29)
where b 1 := z k +1 + (1/t) n k1 and b 2 := s k +1 + (1/t) n k2 . Note
that problem (29) can be decomposed into two problems with respect to w and u :
*
t
< w - b 1 < 22,
2
minimize
< u - b 2 < 22, subject to < u < 2 # p.
u
minimize
< w <1 +
w
(30)
Both problems in (30) can be solved analytically [30]
w k +1 = (b 1 - 1/t1) + - (-b 1 - 1/t1) +,
* u k +1 = min {p, < b
<}
2 2
b2
< b2 <2
,
(31)
where recall that ^ $ h+ is the positive part operator.
Similar to LPs and QPs, the hardware design of the
memristor-based CS solver mainly consists of two parts.
The first part is the memristor-based linear system solver, in which memristor crossbars are only programmed
once since the coefficient matrix C in (28) is independent of ADMM iterations. The second part is the digital or analog implementation of the solution to problem
(31). This requires the calculation of the , 2 norm of a
vector that can be realized using elementary logic or
digital operations; similar to Fig. 5. The ADMM-based
solution exhibits low hardware complexity.
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