%?This?small?matlab?demo?tests?the?Binary?Iterative?Hard?Thresholding?algorithm
%?developed?in:
%
%??“Robust?1-bit?CS?via?binary?stable?embeddings“
%??L.?Jacques?J.?Laska?P.?Boufounos?and?R.?Baraniuk
%??
%?More?precisely?using?paper?notations?two?versions?of?BIHT?are?tested
%?here?on?sparse?signal?reconstruction:
%
%??*?the?standard?BIHT?associated?to?the?（LASSO?like）?minimization?of
%?
%????????min?||?[?y?o?A（u）?]_-?||_1?s.t.?||u||_0?\leq?K????（1）
%
%??*?the?（less?efficient）?BIHT-L2?related?to?
%
%????????min?||?[?y?o?A（u）?]_-?||^2_2?s.t.?||u||_0?\leq?K??（2）?
%
%?where?y?=?A（x）?:=?sign（Phi*x）?are?the?1-bit?CS?measurements?of?a?initial
%?K-sparse?signal?x?in?R^N;?Phi?is?a?MxN?Gaussian?Random?matrix?of?entries
%?iid?drawn?as?N（01）;?[s]_-?equals?to?s?if?s?%?component?wise?on?vectors;?“o“?is?the?Hadamard?product?such?that?
%?（u?o?v）_i?=?u_i*v_i?for?two?vectors?u?and?v.?
%
%?Considering?the?（sub）?gradient?of?the?minimized?energy?in?（1）?and?（2）
%?BIHT?is?solved?through?the?iteration:
%
%?????x^（n+1）?=?H_K（?x^（n）?-?（1/M）*Phi‘*（A（x^（n））?-?y）?）
%
%?while?BIHT-L2?is?solved?through:
%
%?????x^（n+1）?=?H_K（?x^（n）?-?（Y*Phi）‘?*?[（Y*Phi*x^（n））]_-）?）
%
%?with?Y?=?diag（y）?H_K（u）?the?K-term?thresholding?keeping?the?K
%?highest?amplitude?of?u?and?zeroing?the?others.?
%
%?Authors:?J.?Laska?L.?Jacques?P.?Boufounos?R.?Baraniuk
%??????????April?2011

%%?Important?parameters?and?functions

N?=?2000;?%?Signal?dimension
M?=?500;??%?Number?of?measurements
K?=?15;???%?Sparsity

%?Negative?function?[.]_-
neg?=?@（in）?in.*（in?<0）;?

%%?Generating?a?unit?K-sparse?signal?in?R^N?（canonical?basis）

x0?=?zeros（N1）;
rp?=?randperm（N）;
x0（rp（1:K））?=?randn（K1）;?
x0?=?x0/norm（x0）;


%%?Gaussian?sensing?matrix?and?associated?1-bit?sensing

Phi?=?randn（MN）;
A?=?@（in）?sign（Phi*in）;

y?=?A（x0）;

%%?Testing?BIHT

maxiter?=?3000;
htol?=?0;

x?=?zeros（N1）;
hd?=?Inf;

ii=0;
while（htol?	%?Get?gradient
	g?=?Phi‘*（A（x）?-?y）;
	
	%?Step
	a?=?x?-?g;
	
	%?Best?K-term?（threshold）
	[trash?aidx]?=?sort（abs（a）?‘descend‘）;
	a（aidx（K+1:end））?=?0;
	
????%?Update?x
	x?=?a;

	%?Measure?hammning?distance?to?original?1bit?measurements
	hd?=?nnz（y?-?A（x））;
	ii?=?ii+1;
end

%?Now?project?to?sphere
x?=?x/norm（x）;

BIHT_nbiter?=?ii;
BIHT_l2_err?=?norm（x0?-?x）/norm（x0）;
BIHT_Hamming_err?=?nnz（y?-?A（x））;



%%?Testing?BIHT-l2

maxiter?=?3000;
htol?=?0;

x_l2?=?Phi‘*y;
x_l2?=?x_l2/norm（x_l2）;
hd?=?Inf;

%?Update?matrix?（easier?for?computation）
cPhi?=?diag（y）*Phi;
tau?=?1/M;

ii=0;
while?（htol?	%?Compute?Gradient
????g?=?tau*cPhi‘*neg（cPhi*x_l2）;
	
	%?Step
	a?=?x_l2?-?g;
	
	%?Best?K-term?（threshold）
	[trash?aidx]?=?sort（abs（a）?‘descend‘）;
	a（aidx（K+1:end））?=?0;
	
	%?Update?x_l2
	x_l2?=?a;
	
	%?Measure?hammning
	hd?=?nnz（y?-?sign（cPhi*x））;
	ii?=?ii+1;
end

%Now?project?to?sphere
x_l2?=?x_l2/norm（x_l2）;

BIHTl2_nbiter?=?ii;
BIHTl2_l2_err?=?norm（x0?-?x_l2）/norm（x0）;
BIHTl2_Hamming_err?=?nnz（y?-?A（x_l2））;


%%?Plotting?results

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2011-04-22?23:41??demo_BIHT\
?????文件????????6148??2011-04-22?23:41??demo_BIHT\.DS_Store
?????目錄???????????0??2011-04-22?23:41??__MACOSX\
?????目錄???????????0??2011-04-22?23:41??__MACOSX\demo_BIHT\
?????文件??????????82??2011-04-22?23:41??__MACOSX\demo_BIHT\._.DS_Store
?????文件????????3546??2011-04-22?23:40??demo_BIHT\demo_BIHT.m
?????文件??????????82??2011-04-22?23:40??__MACOSX\demo_BIHT\._demo_BIHT.m
?????文件??????106456??2011-04-22?23:31??demo_BIHT\demo_BIHT.pdf
?????文件?????????201??2011-04-22?23:31??__MACOSX\demo_BIHT\._demo_BIHT.pdf
?????目錄???????????0??2011-04-22?23:30??demo_BIHT\html\
?????文件????????6148??2011-04-22?23:25??demo_BIHT\html\.DS_Store
?????目錄???????????0??2011-04-22?23:41??__MACOSX\demo_BIHT\html\
?????文件??????????82??2011-04-22?23:25??__MACOSX\demo_BIHT\html\._.DS_Store
?????文件???????10941??2011-04-22?23:30??demo_BIHT\html\demo_BIHT.html
?????文件?????????570??2011-04-22?23:30??__MACOSX\demo_BIHT\html\._demo_BIHT.html
?????文件???????13788??2011-04-22?23:24??demo_BIHT\html\demo_BIHT.png