Problem 1

Consider the sparse linear model \(Y=X\beta+\epsilon\) with \(Y\in\mathbb{R}^n\), \(X\in\mathbb{R}^{n\times p}\), \(\beta = (.5,-.5,1,-1,2,-2,0,0,...,0)\in\mathbb{R}^p\), \(\epsilon \sim N_n(0,\sigma_\epsilon I_n)\). Independently generate each row of \(X\) from \(N_p(0,\sigma_X I_p)\) with \(\sigma_X^2 = 9\) and \(p=2000\) and generate the rest of data from the linear model with \(n=100\), \(p=2000\), \(\sigma_\epsilon^2=1\). Implement the lasso method by the ADMM algorithm. Check your result with the true \(\beta\) and result from ‘glmnet()’.

library(glmnet)
## Loading required package: Matrix
## 
## Attaching package: 'Matrix'
## The following objects are masked from 'package:tidyr':
## 
##     expand, pack, unpack
## Loaded glmnet 4.1-7
set.seed(1)

##########  Given Info
n = 100 
p = 2000 
variance_eps = 1 
variance_X = 9

epsilons = rnorm(n,mean=0,sd= sqrt(variance_eps))
X = matrix(0, nrow = n, ncol = p)


########  The following is given.  We pretend that we do not know distribution

# We pretend that we do not know distribution for X
for (i in 1:n){
  X[i,] = rnorm(p,mean=0,sd=sqrt(variance_X))
}

# We pretend we do not know beta parameters
Beta_truth = numeric(p)
Beta_truth[1:6] = c(0.5,-0.5,1,-1,2,-2)

#We pretend that we do not know anything regarding distribution of Y
Y = X%*%Beta_truth + epsilons

# We will now estimate Beta parameters using Lasso method using ADMM algorithm

tol = .001
max_steps = 100000

lambda = 5
rho = 10

#initialize alpha, beta, u
alpha = numeric(p); beta = numeric(p); u = numeric(p)
#Start at 0's and then change after
alpha = alpha; beta = beta; u = 1+u

#From slide 32
Sy = function(y,x){
  if (x>y){
    x - y
  }else if (x < -y){
    x + y
  } else{
    0
  }
}


#This finds transpose of X
X_Transpose = t(X) 

#Computes X^T*X + rho * I: 

#The diag function creates diagonal matrix of length p
A = X_Transpose%*%X+diag(x=rho,nrow=p,ncol=p)
#Find inverse using Cholesky decomposition
A_inv = chol2inv(chol(A)) 
# I just need to compute this once
X_Transpose_Y = X_Transpose%*%Y

for (i in 1:max_steps){
  alpha_old = alpha
  beta_old = beta
  u_old = u
 
  #From slide 29
    #I pull A_inv and X_Transpose_Y from above
  alpha = A_inv%*%(X_Transpose_Y+rho*(beta_old-u_old))
 
  #From slide 32
  for (j in 1:p){
    beta[j] = Sy(lambda/rho,alpha[j]+u_old[j])
  }
  
  #From slide 32
  u = u_old + alpha - beta
  r_k = alpha - beta
  
  #Check if L2 norm is less than tolerance level (i.e. convergence)
  if (norm(r_k,"2")<tol){
    break
  }
}

#Record the Best estimators
beta_estimator = beta

#Find how close our beta_estimators are to truth using L2 Norm
Lasso_Result = norm(beta_estimator - Beta_truth,"2")


#fitting X and Y by the Lasso method (default).  It tests 100 lambda values 
fit = glmnet(X,Y) 

#grab beta estimators from glmnet
coefficient_lambda1 = coef(fit,s=0.01) 

#compare beta estimators from glmnet to the truth, leave out intercept
GLMNET_Result = norm(coefficient_lambda1[2:length(coefficient_lambda1)]-Beta_truth,"2")

print("The first 15 Beta hats from Beta hat vector from the Lasso Method are:")
## [1] "The first 15 Beta hats from Beta hat vector from the Lasso Method are:"
print(beta_estimator[1:15])
##  [1]  0.47287066 -0.42736003  0.93875362 -0.93864510  1.86574037 -1.97863222
##  [7]  0.00000000  0.00000000  0.00000000 -0.01615163  0.00000000  0.00000000
## [13]  0.00000000  0.00000000  0.00000000
print("For remaining beta hats, please see my vector beta_estimator")
## [1] "For remaining beta hats, please see my vector beta_estimator"
print(paste("The L2 norm of Beta hat vector using Lasso Method minus the true Beta is:", Lasso_Result))
## [1] "The L2 norm of Beta hat vector using Lasso Method minus the true Beta is: 0.267926843394215"
print(paste("The L2 norm of Beta hat vector using glmnet minus the true Beta is:", GLMNET_Result))
## [1] "The L2 norm of Beta hat vector using glmnet minus the true Beta is: 0.232988830652029"