Compressed Sensing Overview

True information (but pretend don' t know the true deviations, which we want to solve for)

Ncoins=20
Nsets=6

truedeviations=ConstantArray[0,Ncoins];
truedeviations[[4]]=0.1;
truedeviations[[7]]=-0.2;
truedeviations

Phi=RandomInteger[{0,1},{Nsets,Ncoins}];
Phi//MatrixForm

Result of weighing random groups of coins

b=Phi.truedeviations

Try different approaches to solving for the deviations
Solving Phi.x=b yields infinitely many solutions (Ncoins minus Nsets degrees of freedom)

LinearSolve[Phi,b]

NullSpace[Phi]

Minimize size of deviation vector x given Phi.x = b :

soln=Minimize[{Norm[Array[x,Ncoins]],Phi.Array[x,Ncoins]==b},Array[x,Ncoins]]

ListPlot[Array[x,Ncoins]/.soln[[2]],Filling->Axis,PlotStyle->PointSize[Large],PlotRange->All]

soln=Minimize[{Norm[Array[x,Ncoins],1],Phi.Array[x,Ncoins]==b},Array[x,Ncoins]]

ListPlot[Array[x,Ncoins]/.soln[[2]],Filling->Axis,PlotStyle->PointSize[Large],PlotRange->All]

Try bigger example

Ncoins=100
Nsets=16

truedeviations=ConstantArray[0,Ncoins];
truedeviations[[4]]=0.1;
truedeviations[[7]]=-0.2;

Phi=RandomInteger[{0,1},{Nsets,Ncoins}];

Result of weighing random groups of coins

b=Phi.truedeviations

Minimize size of deviation vector x given Phi.x = b :

soln=Minimize[{Norm[Array[x,Ncoins]],Phi.Array[x,Ncoins]==b},Array[x,Ncoins]]

ListPlot[Array[x,Ncoins]/.soln[[2]],Filling->Axis,PlotStyle->PointSize[Large],PlotRange->All]

soln=Minimize[{Norm[Array[x,Ncoins],1],Phi.Array[x,Ncoins]==b},Array[x,Ncoins]]

ListPlot[Array[x,Ncoins]/.soln[[2]],Filling->Axis,PlotStyle->PointSize[Large],PlotRange->All]