def omp(D,x,a,L=None, tol=1e-6):
  """ perform orthogonal matching pursuit
  
      inputs:
        D: dictionary (k x d numpy array s.t. k>d)
        x: image/data vector (1 x d numpy array)
        L: maximum sparse coefficients (default: 0.5*k)
        a: sparse vector (1 x k numpy array)

      outputs:
        a: updated sparse vector (k x 1 numpy array)        
  """
  # dims
  k, d = D.shape
 
  # default parameter
  if L is None:
      L = 0.5 * k

  # *** init parameters here
    
  # *** put code for omp here ***
  
  return a

def ksvd(X, **args):
    ''' k-svd algorithm
    
        inputs:
            x: images (n x d array)
            D: optional dictionary.  If D is None, then dictionary is learned.  Otherwise,
               only sparse coefficients are learned. (default None)
            args:
                k: number of latent variables (defualt 20)
                L: sparsity parameter
                nsteps: maximum number of iterations (default 200)
                tol: toleraance for convergence (default 1e-3)
        
        returns:
            J: objective error
            D: dictionary (k x d numpy array)
            A: sparse coefficients (n x k numpy array)
    '''

    # default parameters
    if not len(args):
        args['k'] = 1024
        args['nsteps'] = 200
        args['L'] = 100
        args['tol'] = 1e-3

    nsteps = args['nsteps']
    k = args['k']
    L = args['L']
    tol = args['tol']
    
    # dims 
    n, d = X.shape

    # ***initialize variables here***
    
    # *** start main loop ***
    for step in range(nsteps):
        # *** test for convergence here ***
        
        # display progress
        print('{} / {} - J: {}'.format(step, nsteps, J))

        # *** sparse coding using orthogonal matching pursuit here ***
            
        # *** dictionary update here ***
        
    return J, D, A