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

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