I have taken a course on optimization and much was said but not elaborated on role of sparsity in the data. I was led to believe that optimization algorithms could be made more efficiently with respect to sparsity.
But looking at some notes on so called "sparse optimization" http://www.math.ucla.edu/~wotaoyin/summer2013/slides/Lec02_BasicSparseOptimizationModels.pdf I have not either a definition of what it means for the data to be sparse, nor have I seen any alternative algorithms.
Can someone please explain the role of sparsity in optimization and perhaps provide a small example?
In many problems there are a large number of variables and constraints, but each constraint will only involve a small number of variables. Therefore nearly all of the entries of the coefficient matrix will be $0$: that says the matrix is sparse. A large matrix (say with a million variables and constraints) would never be able to fit in the computer's memory if you needed space for each entry. A sparse matrix can fit because you only need to store the nonzero entries. But you need to be careful with the algorithms used, to try to keep the matrix sparse throughout the computation.