bpdq_1d : Main implementation of BPDQ algorithm x_bpdq = bpdq_1d(yq,A,epsilon,p,varargin); This solves the BPDQ program x_bpdq = argmin_x ||x||_1 s.t. ||yq - A*x||_p <= epsilon using the Douglas-Rachford algorithm. This is the implementation of the method described in "Dequantizing Compressed Sensing : When Oversampling and Non-Gaussian Constraints Combine" by Laurent Jacques, David Hammond, M. Jalal Fadili ( submitted to IEEE Transactions on Signal Processing) Inputs: yq - quantized measurements A - sensing matrix epsilon - lpball radius, chosen so that original signal is feasible with high probability p - BPDQ moment Selectable control parameters : dr_gamma, dr_lambda - DR algorithm parameters dr_maxiter - maximum number of DR iterations dr_relerr_thresh - relatize error threshold to terminate DR iteration dr_verbosity - 1 to enable output, 0 to supress fca_maxiter - max number of iterations for fca iteration (f composed with A - iteration to compute prox(f(A(x))) : see bpdq_f_comp_A.m for details fca_relerr_thresh - relative error threshold to terminate fca iteration fca_verbosity - 1 to enable output, 0 to supress Outputs: x_bpdq - solution to BPDQ program D - debugging structure containing field dr_relerr_save, for verifying empirical convergence of algorithm This file is part of BPDQ Toolbox (Basis Pursuit DeQuantizer) Copyright (C) 2009, the BPDQ Team (see the file AUTHORS distributed with this library) (See the notice at the end of the file.)
0001 % bpdq_1d : Main implementation of BPDQ algorithm 0002 % 0003 % x_bpdq = bpdq_1d(yq,A,epsilon,p,varargin); 0004 % 0005 % This solves the BPDQ program 0006 % x_bpdq = argmin_x ||x||_1 s.t. ||yq - A*x||_p <= epsilon 0007 % using the Douglas-Rachford algorithm. 0008 % 0009 % This is the implementation of the method described in 0010 % "Dequantizing Compressed Sensing : When Oversampling and Non-Gaussian 0011 % Constraints Combine" 0012 % by Laurent Jacques, David Hammond, M. Jalal Fadili 0013 % ( submitted to IEEE Transactions on Signal Processing) 0014 % 0015 % Inputs: 0016 % yq - quantized measurements 0017 % A - sensing matrix 0018 % epsilon - lpball radius, chosen so that original signal is 0019 % feasible with high probability 0020 % p - BPDQ moment 0021 % 0022 % Selectable control parameters : 0023 % dr_gamma, dr_lambda - DR algorithm parameters 0024 % dr_maxiter - maximum number of DR iterations 0025 % dr_relerr_thresh - relatize error threshold to terminate DR iteration 0026 % dr_verbosity - 1 to enable output, 0 to supress 0027 % fca_maxiter - max number of iterations for fca iteration 0028 % (f composed with A - iteration to compute prox(f(A(x))) : see 0029 % bpdq_f_comp_A.m for details 0030 % fca_relerr_thresh - relative error threshold to terminate fca iteration 0031 % fca_verbosity - 1 to enable output, 0 to supress 0032 % 0033 % Outputs: 0034 % x_bpdq - solution to BPDQ program 0035 % D - debugging structure containing field dr_relerr_save, for 0036 % verifying empirical convergence of algorithm 0037 % 0038 % This file is part of BPDQ Toolbox (Basis Pursuit DeQuantizer) 0039 % Copyright (C) 2009, the BPDQ Team (see the file AUTHORS distributed with 0040 % this library) (See the notice at the end of the file.) 0041 0042 function [x_bpdq,D] = bpdq_1d(yq,A,epsilon,p,varargin) 0043 control_params={'dr_gamma',.05,... 0044 'dr_lambda',.5,... 0045 'dr_maxiter',500,... 0046 'dr_relerr_thresh',1e-6,... 0047 'dr_verbosity',0,... 0048 'fca_maxiter',500,... 0049 'fca_relerr_thresh',1e-6,... 0050 'fca_verbosity',0}; 0051 0052 argselectAssign(control_params); 0053 argselectCheck(control_params,varargin); 0054 argselectAssign(varargin); 0055 0056 % c is upper frame bound for frame corresponding to matrix A 0057 % (used for iteration for composition, ref 0058 % Jacques et. al. Lemma 4) 0059 c= max(svd(A))^2; 0060 0061 % Sensing data 0062 [M,N] = size(A); 0063 opA = @(in) A*in; 0064 opAt = @(in) A'*in; 0065 0066 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 0067 % define prox operators 0068 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 0069 0070 % f1 is ||yq-A*x||_p, prox computed iteratively 0071 % with function composition and lp_ball projection 0072 % (tgamma may be discarded as f1(x) has only zero and infinite values) 0073 lpball_prox = @(u,tgamma) bpdq_proj_lpball_mex(u,yq,epsilon,p); 0074 prox1 = @(u,tgamma) bpdq_prox_f_comp_A(u,lpball_prox,opA,opAt,c,... 0075 'fca_maxiter',fca_maxiter,... 0076 'fca_relerr_thresh',fca_relerr_thresh,... 0077 'fca_verbosity',fca_verbosity); 0078 % f2 is ||x||_1, prox is soft thresholding 0079 prox2= @(u,tgamma) bpdq_soft_threshold(u,tgamma); 0080 0081 x0=zeros(N,1); % initialize at zero 0082 % call douglas rachford iteration with defined prox operators 0083 [x_bpdq,relerr_save]=bpdq_d_r_iter(prox1,prox2,dr_gamma,dr_lambda,x0,... 0084 'dr_maxiter',dr_maxiter,... 0085 'dr_relerr_thresh',dr_relerr_thresh,... 0086 'dr_verbosity',dr_verbosity); 0087 D.dr_relerr_save=relerr_save; 0088 0089 % The BPDQ Toolbox is free software: you can redistribute it and/or modify 0090 % it under the terms of the GNU General Public License as published by 0091 % the Free Software Foundation, either version 3 of the License, or 0092 % (at your option) any later version. 0093 % 0094 % The BPDQ Toolbox is distributed in the hope that it will be useful, 0095 % but WITHOUT ANY WARRANTY; without even the implied warranty of 0096 % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 0097 % GNU General Public License for more details. 0098 % 0099 % You should have received a copy of the GNU General Public License 0100 % along with The BPDQ Toolbox. If not, see <http://www.gnu.org/licenses/>.