The short answer: Sparse Coding is just one of the available techniques for training Autoencoders (the "Sparse Autoencoder"), but there are other options. All are useful for extracting features. Now a longer answer for each of your questions.

Sparse coding is defined as learning an over-complete set of basis vectors to represent input vectors (<-- why do we want this)

First, at least since (Hubel & Wiesel, 1968) it's known that in the V1 region there are specific cells which respond maximally to edge-like stimulus (besides having others "useful" properties). Sparse Coding is a model which explains well many of the observed characteristics of this system. See (Olshausen & Field, 1996) for more details.

Second, it's being shown to be useful technique for feature extraction in Machine Learning and to yield good results in transfer learning tasks. Raina et al. (2007) showed that a set of "basis vectors" (features, as pen-strokes and edges) learned with a training set composed of hand-written characters improve classification in a hand-written digits recognition task. Later Sparse Coding has been used to train "deep" models, stacking layers of sparse feature detectors to create a "sparse deep belief net" (Lee et al., 2007). More recently astonishing results in image recognition was achieved using sparse coding to construct a model with several layers (the famous "Google Brain"), which was capable of distinguish a image of a cat in a purely unsupervised manner (Le et al., 2013).

Third, it's probably possible to use the learned basis to perform compression. A haven't seen anyone really doing it though.

What are the difference between sparse coding and autoencoder?

An autoencoder is a model which tries to reconstruct its input, usually using some sort of constraint. Accordingly to Wikipedia it "is an artificial neural network used for learning efficient codings". There's nothing in autoencoder's definition requiring sparsity. Sparse coding is one of the available techniques (constraints), but there are others, for example Denoising Autoencoders, Contractive Autoencoders and RBMs. All makes the network learn good representations of the input (that are also commonly also "sparse").

When will we use sparse coding and autoencoder?

You're probably interested in using an auto-encoder for feature extraction and/or pre-training of deep networks. If you implement an autoencoder with the sparsity constraint, you'll be using both.

In neuroscience the term Neural Coding is used to refer to the patterns of electrical activity of neurons induced by a stimulus. Sparse Coding by its turn is one kind of pattern. A code is said to be sparse when a stimulus (like an image) provokes the activation of just a relatively small number of neurons, that combined represent it in a sparse way. In machine learning the same optimization constraint used to create a sparse code model can be used to implement Sparse Autoencoders, which are regular autoencoders trained with a sparsity constraint. Bellow more detailed explanations for each of your questions are given.

Sparse coding is defined as learning an over-complete set of basis vectors to represent input vectors (<-- why do we want this)

First, at least since (Hubel & Wiesel, 1968) it's known that in the V1 region there are specific cells which respond maximally to edge-like stimulus (besides having others "useful" properties). Sparse Coding is a model which explains well many of the observed characteristics of this system. See (Olshausen & Field, 1996) for more details.

Second, it's being shown that the model which describes sparse coding is a useful technique for feature extraction in Machine Learning and yields good results in transfer learning tasks. Raina et al. (2007) showed that a set of "basis vectors" (features, as pen-strokes and edges) learned with a training set composed of hand-written characters improves classification in a hand-written digits recognition task. Later Sparse Coding based models has been used to train "deep" networks, stacking layers of sparse feature detectors to create a "sparse deep belief net" (Lee et al., 2007). More recently astonishing results in image recognition was achieved using sparse coding based models to construct a network with several layers (the famous "Google Brain"), which was capable of distinguish a image of a cat in a purely unsupervised manner (Le et al., 2013).

Third, it's probably possible to use the learned basis to perform compression. A haven't seen anyone really doing it though.

What are the difference between sparse coding and autoencoder?

An autoencoder is a model which tries to reconstruct its input, usually using some sort of constraint. Accordingly to Wikipedia it "is an artificial neural network used for learning efficient codings". There's nothing in autoencoder's definition requiring sparsity. Sparse coding based contraints is one of the available techniques, but there are others, for example Denoising Autoencoders, Contractive Autoencoders and RBMs. All makes the network learn good representations of the input (that are also commonly "sparse").

When will we use sparse coding and autoencoder?

You're probably interested in using an auto-encoder for feature extraction and/or pre-training of deep networks. If you implement an autoencoder with the sparsity constraint, you'll be using both.