import numpy as np
import numpy.linalg as la
def soft(x,t):
y=np.abs(x)
y-=t
np.maximum(y,0,y)
y/=(y+t)
y*=x
return y
def fista(A,b,tau,L0=1e-4,eta=2,tol=1e-6):
H=np.dot(A.T,A)
c=np.dot(A.T,b)
L=L0
x=c
y=x
t=1
cost=la.norm(b-np.dot(A,x))**2/2+tau*la.norm(x,1)
while True:
x0=x
cost0=cost
fy=la.norm(b-np.dot(A,y))**2
fpy=np.dot(H,y)-c
while True:
x=soft(y-fpy/L,tau/L)
cost=la.norm(b-np.dot(A,x))**2/2+tau*la.norm(x,1)
if cost<=fy+np.dot(x-y,fpy)+L*la.norm(x-y)**2/2+tau*la.norm(x,1):
break
L*=eta
if abs((cost-cost0)/cost)<tol:
break
t0=t
t=(1+np.sqrt(1+4*t0**2))/2
y=x+(t0-1)/t*(x-x0)
return x
import numpy.linalg as la
def soft(x,t):
y=np.abs(x)
y-=t
np.maximum(y,0,y)
y/=(y+t)
y*=x
return y
def fista(A,b,tau,L0=1e-4,eta=2,tol=1e-6):
H=np.dot(A.T,A)
c=np.dot(A.T,b)
L=L0
x=c
y=x
t=1
cost=la.norm(b-np.dot(A,x))**2/2+tau*la.norm(x,1)
while True:
x0=x
cost0=cost
fy=la.norm(b-np.dot(A,y))**2
fpy=np.dot(H,y)-c
while True:
x=soft(y-fpy/L,tau/L)
cost=la.norm(b-np.dot(A,x))**2/2+tau*la.norm(x,1)
if cost<=fy+np.dot(x-y,fpy)+L*la.norm(x-y)**2/2+tau*la.norm(x,1):
break
L*=eta
if abs((cost-cost0)/cost)<tol:
break
t0=t
t=(1+np.sqrt(1+4*t0**2))/2
y=x+(t0-1)/t*(x-x0)
return x