Online Dictionary Learning for Sparse Coding

     When we write a sentence, we would like to use less words to express what we want to say. In sparse coding, if we have some vectors (called D), we are likely to do simple linear combination of these vectors to represent an image.
    Based on our goal, we have the following cost function:

    The loss function acts like a distance function, we should use D to represent images but don't want lose much information. Suppose the each x is m-dimensional vector, then D is a m*k-dimensional matrix, where k is smaller than the numbers of images.(e.g. k=200, n=100,000)
    The detail of the cost function is as follow:

    The second term is the regularization term, if we decrease alpha, make D larger, we can minimize the second term, but it helps nothing. We hope that we have the simplest alpha, so we rewrite the object function:  

    The above formula limits the size for each column of D, and the cost function follows the limitation:

    
    In the paper, we use online learning, which means we add an images each iteration, then update alpha and D, here is the algorithm:

     In the procedure of updating D, we use D_(t-1) as the initial point, here is the algorithm of updating D.

    The length for each column of D would be less than 1, which follows our constraint. Here we discuss some conditions we may counter:
    (1) In real data, we may have fewer images, which means we may select the same image in different iterations, suppose at time t0 we draw an image, at time t we draw the same image again, here is the way we update A:

    We discard the information of time t0. In the implementation, we hardly memory the history of images drawed.
   (2) Here we use a batch of images to update:

   (3) Some columns of D contain nothing, we should discard the columns when we update D.