Structured low complexity data mining
Jason Jo · Texas ScholarWorks (Texas Digital Library) · 2015
Due to the rapidly increasing dimensionality of modern datasets many classical approximation algorithms have run into severe computational bottlenecks.This has often been referred to as the "curse of dimensionality."To combat this, low complexity priors have been used as they enable us to design efficient approximation algorithms which are capable of scaling up to these modern datasets.Typically the reduction in computational complexity comes at the expense of accuracy.However, the tradeoffs have been relatively advantageous to the computational scientist.This is typically referred to as the "blessings of dimensionality."Solving large underdetermined systems of linear equations has benefited greatly from the sparsity low complexity prior.A priori, solving a large underdetermined system of linear equations is severely ill-posed.However, using a relatively generic class of sampling matrices, assuming a sparsity prior can yield a well-posed linear system of equations.In particular, various greedy v