Orthogonal Greedy Algorithm with Thresholding in Compressed % Sensing
Mingrui~Yang
Greed is good. However, the tighter you squeeze, the less you have. In this paper, a less greedy algorithm for sparse signal reconstruction in compressive sensing, named orthogonal matching pursuit with thresholding is studied. Using the global 2-coherence , which provides a ``bridge" between the well known mutual coherence and the restricted isometry constant, the performance of orthogonal matching pursuit with thresholding is analyzed and more general results for sparse signal reconstruction are obtained. It is also shown that given the same assumption on the coherence index and the restricted isometry constant as required for orthogonal matching pursuit, the thresholding variation gives exactly the same reconstruction performance \mymy{with significantly less complexity}. % In this paper we define a new coherence index, named 2-coherence, of a given % dictionary and study its relationship with the traditional mutual % coherence and the restricted isometry constant. By exploring this % relationship, we obtain more general results on sparse signal reconstruction using % greedy algorithms in the compressive sensing (CS) framework. In % particular, we obtain an improved bound over the best known results % on the restricted isometry constant for % successful recovery of sparse signals using orthogonal matching pursuit (OMP). % We also initialized a study of a thresholding type greedy algorithm named orthogonal matching % pursuit with thresholding (OMPT), which is more feasible in practice than OMP. We % analyze its performance in CS framework for both noiseless and noisy cases in % terms of coherence indices and the restricted isometry constant. We show % that given the same assumptions as required for OMP, it achieves exactly the same % reconstruction performance as OMP.
TSP_version3_single_column.tex

%% bare_jrnl.tex
%% V1.4
%% 2012/12/27
%% by Michael Shell
%% see http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.8 or later) with an IEEE journal paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/



% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/


%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE! 
%% User assumes all risk.
%% In no event shall IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%
%% File list of work: IEEEtran.cls, IEEEtran_HOWTO.pdf, bare_adv.tex,
%%                    bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex,
%%                    bare_jrnl_transmag.tex
%%*************************************************************************

% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print - the typesetting of the document will not typically be
% affected with changes in paper size (but the bottom and side margins will).
% Use the testflow package mentioned above to verify correct handling of
% both paper sizes by the user's LaTeX system.
%
% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
\documentclass[draftclsnofoot, onecolumn]{IEEEtran}
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[journal]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off
% such as if a citation ever needs to be enclosed in parenthesis.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.






% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  % \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation
% can be obtained at: 
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found at:
% http://www.ctan.org/tex-archive/info/epslatex/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex

  \usepackage[pdftex]{graphicx}



% *** MATH PACKAGES ***
%
\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/

\usepackage{amsfonts}
\usepackage{amssymb,framed}
\usepackage{amsthm}

\newtheorem{thm}{Theorem}[section]
% \renewcommand\thethm{\arabic{section}.\arabic{thm}}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{pro}[thm]{Proposition}
%\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{rmk}[thm]{Remark}
%\theoremstyle{plain}

\DeclareMathOperator*{\supp}{supp}
\DeclareMathOperator*{\argmin}{arg\,min}


% *** SPECIALIZED LIST PACKAGES ***
%
% \usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/

\usepackage{algorithm}
\usepackage{algorithmic}


% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.




% *** SUBFIGURE PACKAGES ***
%\ifCLASSOPTIONcompsoc
%  \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
%\else
%  \usepackage[caption=false,font=footnotesize]{subfig}
%\fi
% subfig.sty, written by Steven Douglas Cochran, is the modern replacement
% for subfigure.sty, the latter of which is no longer maintained and is
% incompatible with some LaTeX packages including fixltx2e. However,
% subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty
% which will override IEEEtran.cls' handling of captions and this will result
% in non-IEEE style figure/table captions. To prevent this problem, be sure
% and invoke subfig.sty's "caption=false" package option (available since
% subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls
% handling of captions.
% Note that the Computer Society format requires a larger sans serif font
% than the serif footnote size font used in traditional IEEE formatting
% and thus the need to invoke different subfig.sty package options depending
% on whether compsoc mode has been enabled.
%
% The latest version and documentation of subfig.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/


%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Do not use the stfloats baselinefloat ability as IEEE does not allow
% \baselineskip to stretch. Authors submitting work to the IEEE should note
% that IEEE rarely uses double column equations and that authors should try
% to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty
% packages (also by Sigitas Tolusis) as IEEE does not format its papers in
% such ways.
% Do not attempt to use stfloats with fixltx2e as they are incompatible.
% Instead, use Morten Hogholm'a dblfloatfix which combines the features
% of both fixltx2e and stfloats:
%
% \usepackage{dblfloatfix}
% The latest version can be found at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/dblfloatfix/


\usepackage{enumerate}


%\ifCLASSOPTIONcaptionsoff
%  \usepackage[nomarkers]{endfloat}
% \let\MYoriglatexcaption\caption
% \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
%\fi
% endfloat.sty was written by James Darrell McCauley, Jeff Goldberg and 
% Axel Sommerfeldt. This package may be useful when used in conjunction with 
% IEEEtran.cls'  captionsoff option. Some IEEE journals/societies require that
% submissions have lists of figures/tables at the end of the paper and that
% figures/tables without any captions are placed on a page by themselves at
% the end of the document. If needed, the draftcls IEEEtran class option or
% \CLASSINPUTbaselinestretch interface can be used to increase the line
% spacing as well. Be sure and use the nomarkers option of endfloat to
% prevent endfloat from "marking" where the figures would have been placed
% in the text. The two hack lines of code above are a slight modification of
% that suggested by in the endfloat docs (section 8.4.1) to ensure that
% the full captions always appear in the list of figures/tables - even if
% the user used the short optional argument of \caption[]{}.
% IEEE papers do not typically make use of \caption[]'s optional argument,
% so this should not be an issue. A similar trick can be used to disable
% captions of packages such as subfig.sty that lack options to turn off
% the subcaptions:
% For subfig.sty:
% \let\MYorigsubfloat\subfloat
% \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
% However, the above trick will not work if both optional arguments of
% the \subfloat command are used. Furthermore, there needs to be a
% description of each subfigure *somewhere* and endfloat does not add
% subfigure captions to its list of figures. Thus, the best approach is to
% avoid the use of subfigure captions (many IEEE journals avoid them anyway)
% and instead reference/explain all the subfigures within the main caption.
% The latest version of endfloat.sty and its documentation can obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/endfloat/
%
% The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
% later in the document, say, to conditionally put the References on a 
% page by themselves.




% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/url/
% Basically, \url{my_url_here}.




% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}

\usepackage{color}

\newcommand{\my}[1]{{\color{black}{#1}}}
\newcommand{\mymy}[1]{{\color{black}{#1}}}
\newcommand{\myIII}[1]{{\color{black}{#1}}}

\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
% Do not put math or special symbols in the title.
% \title{Orthogonal Greedy Algorithm with Thresholding in Compressed
% Sensing}
\title{Orthogonal Matching Pursuit with Thresholding and its
  Application in Compressive Sensing}
%
%
% author names and IEEE memberships
% note positions of commas and nonbreaking spaces ( ~ ) LaTeX will not break
% a structure at a ~ so this keeps an author's name from being broken across
% two lines.
% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
%

\author{Mingrui~Yang,~\IEEEmembership{Member,~IEEE,}
        and~Frank~de~Hoog
        % <-this % stops a space
\thanks{Mingrui Yang is with Autonomous System Lab, Digital
  Productivity Flagship, CSIRO, Australia (email: mingrui.yang@csiro.au).}% <-this % stops a space
\thanks{Frank de Hoog is with Digital
  Productivity Flagship, CSIRO, Australia.}
% % <-this % stops a space
% \thanks{Manuscript received mmm dd, yyyy; revised mmm dd, yyyy.}
}

% note the % following the last \IEEEmembership and also \thanks - 
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
% 
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
% "AB" then you have to do: "\textbf{A}\textbf{B}"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.



% The paper headers
% \markboth{Journal of \LaTeX\ Class Files,~Vol.~x, No.~x, Month~yyyy}%
% {Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for Journals}
% The only time the second header will appear is for the odd numbered pages
% after the title page when using the twoside option.
% 
% *** Note that you probably will NOT want to include the author's ***
% *** name in the headers of peer review papers.                   ***
% You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
% you desire.




% If you want to put a publisher's ID mark on the page you can do it like
% this:
%\IEEEpubid{0000--0000/00\$00.00~\copyright~2012 IEEE}
% Remember, if you use this you must call \IEEEpubidadjcol in the second
% column for its text to clear the IEEEpubid mark.



% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}


% make the title area
\maketitle

% As a general rule, do not put math, special symbols or citations
% in the abstract or keywords.
\begin{abstract}
Greed is good. However, the tighter you squeeze, the less you
have. In this paper, a
less greedy algorithm for sparse signal reconstruction in compressive sensing, named orthogonal matching pursuit with
thresholding is studied. Using the
global 2-coherence , which provides a ``bridge" between the well known mutual coherence and the restricted isometry constant, the performance
of orthogonal matching pursuit with thresholding is analyzed and more
general results for sparse signal reconstruction are obtained. It is also
shown that given the same assumption on the coherence index and the
restricted isometry constant as required for orthogonal matching
pursuit, the thresholding variation gives exactly the same
reconstruction performance \mymy{with significantly less complexity}. 

% In this paper we define a new coherence index, named \emph{2-coherence}, of a given
% dictionary and study its relationship with the traditional mutual
% coherence and the restricted isometry constant. By exploring this
% relationship, we obtain more general results on sparse signal reconstruction using
% greedy algorithms in the compressive sensing (CS) framework. In
% particular, we obtain an improved bound over the best known results
% on the restricted isometry constant for
% successful recovery of sparse signals using orthogonal matching pursuit (OMP).

% We also initialized a study of a thresholding type greedy algorithm named orthogonal matching
% pursuit with thresholding (OMPT), which is more feasible in practice than OMP. We
% analyze its performance in CS framework for both noiseless and noisy cases in
% terms of coherence indices and the restricted isometry constant. We show
% that given the same assumptions as required for OMP, it achieves exactly the same
% reconstruction performance as OMP.
\end{abstract}

% Note that keywords are not normally used for peerreview papers.
\begin{IEEEkeywords}
Compressive sensing, mutual coherence, global 2-coherence, restricted isometry
property, orthogonal matching pursuit (OMP), orthogonal matching
pursuit with thresholding (OMPT).
\end{IEEEkeywords}






% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



\section{Introduction}
% % The very first letter is a 2 line initial drop letter followed
% % by the rest of the first word in caps.
% % 
% % form to use if the first word consists of a single letter:
% % \IEEEPARstart{A}{demo} file is ....
% % 
% % form to use if you need the single drop letter followed by
% % normal text (unknown if ever used by IEEE):
% % \IEEEPARstart{A}{}demo file is ....
% % 
% % Some journals put the first two words in caps:
% % \IEEEPARstart{T}{his demo} file is ....
% % 
% % Here we have the typical use of a "T" for an initial drop letter
% % and "HIS" in caps to complete the first word.
% \IEEEPARstart{T}{his} demo file is intended to serve as a ``starter file''
% for IEEE journal papers produced under \LaTeX\ using
% IEEEtran.cls version 1.8 and later.
% % You must have at least 2 lines in the paragraph with the drop letter
% % (should never be an issue)
% I wish you the best of success.

% \hfill mds
 
% \hfill December 27, 2012

\IEEEPARstart{C}{ompressive} sensing (CS) \cite{CandesRombergTao:06,
  Candes2006:Optimal, Do} is a recently developed and fast growing field
of research. Given that the signal of interest
is sparse in a certain basis or tight frame, it provides a new sampling scheme that breaks the
conventional Shannon-Nyquist sampling rate
\cite{Shannon1949:samplingtheorem}, which requires sampling at a rate
at least twice the bandwidth of the signal for successful
recovery. % Without loss of generality, let us assume that the signal of
% interest is sparse by itself. Then the CS problem can be
% formulated as follows. For a vector $a \in \mathbb{R}^d$, let
% $\|a\|_0$ denote the $\ell_0$ ``norm'' of $a$, which counts the number of
% nonzero entries in $a$. Then $a$ is \emph{$k$-sparse} if $\|a\|_0
% \le k$. Let $\Phi\in \mathbb{R}^{n\times d}$ ($n \ll d$) be the
% sampling (sensing) matrix. Then $f = \Phi a$ ($f\in \mathbb{R}^n$) is
% called the measurement vector. The goal is to recover the sparse
% signal $a$ from $f$ by solving the
% following $\ell_0$ minimization problem
\my{In its simplest form, compressive sensing addresses the problem of
finding the sparsest problem solution to a set of underdetermined
equations. That is, it addresses the following $\ell_0$ minimization problem
\begin{align}\label{eqn:l0_minimization}
  \min_a \|a\|_0 \mbox{ subject to } f = \Phi a.
\end{align}
where $\|a\|_0$ denotes the $\ell_0$ ``norm'' of $a$, which counts the
number of nonzero elements of $a$, and $\Phi \in \mathbb{R}^{n\times
  d}$ ($n \ll d$). The vector $a$ is said to be $k$-sparse if $\|a\|_0
\le k$.} Candes and Tao~\cite{Candes2005:LP} have established that it
is sufficient to require all submatrices consisting of
arbitrary $2k$ columns of $\Phi$ to have full rank for the $\ell_0$
minimization problem~\eqref{eqn:l0_minimization} to have a unique
$k$-sparse solution. However, finding this solution is, in general, an
NP-hard problem. 

Fortunately, researchers have proposed several approaches to address this
problem, which fall into two main categories. The
first one is to relax the $\ell_0$ minimization problem to an $\ell_1$
minimization
problem~\cite{Candes2005:LP,Candes:08,Foucart2009395,Foucart201097,5290058,5550400,Mo2011460},
which can be solved in polynomial time. The other stream of work is to
use heuristic approaches, such as greedy algorithms, to approximate
the solution of the $\ell_0$ minimization problem~\cite{Gilbert:2003:AFO:644108.644149, DET2, 1337101, DET,
  Needell2009301, 4839056, 5419092, Blumensath2009265,
  Foucart:2011:HTP:2340478.2340494, 6145475}. The analyses of all of these
algorithms depend on properties of the sampling (sensing) matrix
$\Phi$ and two important metrics here are coherence measures and the restricted isometry constant (RIC), both of which are defined below. A useful bridge between these two metrics has been defined in~\cite{YangdeHoog:2014} and %  In these papers, researchers have
% adopted both coherence indices and the restricted isometry constant (RIC) to analyze the performance
% of both streams. In addition, the bridge between coherence indices and
% the RIC has been established in~\cite{YangdeHoog:2014}, and 
used to
study the reconstruction performance of the weak orthogonal matching
pursuit (WOMP) and the orthogonal matching pursuit (OMP).

In this paper, we continue the study of greedy type algorithms, but in a
different flavor. OMP updates an $s$-term approximation of the measurement vector $f$ a step
at a time, adding to an existing $(s-1)$-term set a new term in a
greedy fashion, aiming to
minimize the $\ell_2$ error over all possible combinations of the $s$
terms. However, it is known (see for
instance~\cite{Temlyakov:11}) that the most computationally expensive
step of all greedy algorithms is the greedy step, which calculates in
each iteration the inner products between the residual and all the
atoms from the dictionary and finds the maximum of them. In this
sense, greed is good,  but less greed could be better. 

Here we study a thresholding greedy algorithm called orthogonal matching pursuit with thresholding
(OMPT), which replaces
the expensive greedy step by a thresholding step. It
only needs to calculate the norm of the residual once in each
iteration and uses it as a threshold. We show that by carefully
choosing the thresholding parameter, OMPT is able to recover the $k$
correct support of the ideal signal in presence of noise,
and obtain exact recover of the $k$-sparse signal in noiseless case,
both in $k$ iterations. In addition, by applying the global 2-coherence~\cite{YangdeHoog:2014}, we show that it maintains exactly the same
reconstruction performance as OMP under the same assumptions on
coherence indices and the RIC, for both noisy and noiseless
scenario. % More details are given in the following sections.

\my{The main contributions of this paper can be summarized as
  follows. Greedy algorithms such as OMP and WOMP have been
  studied intensively in the signal processing community. However,
  few thresholding type greedy algorithms have been studied for
  CS. In this paper we analyze the recovery performance and
  convergence of OMPT using the global 2-coherence and the RIC and show
  that OMPT retains exactly the same recovery performance as OMP given
  the same assumption on these two metrics. Specifically, in
Theorem~\ref{thm:ompt_noiseless} and Theorem~\ref{thm:ompt_noisy}, the
recovery properties for OMPT on sparse signals are established for noiseless and noisy cases
respectively, given optimal choices for the threshold
parameter. The convergence of OMPT in presence of noise for
general choice of the threshold parameter
is then analyzed in Theorem~\ref{thm:ompt_convergence}. It is also shown in Corollary~\ref{cor:ompt} that by
carefully choosing the threshold, OMPT has the same reconstruction
performance as OMP. Precisely, the bound on the RIC for OMPT to succeed
is exactly the same as the best known bound for OMP established
in~\cite{YangdeHoog:2014}. As far as we are aware, these results have not been presented in the literature previously.}


\section{Preliminaries and Notation}

Before moving on to the main results of this paper, we need some
preliminaries and notation. Without loss of generality, assume that the columns of the
matrix $\Phi$ are normalized such that for any column
$\phi_i\in\Phi$, $\|\phi_i\|_2 = 1$. We sometimes also refer to the matrix
$\Phi$ as a dictionary, whose columns are called atoms. 

\subsection{Some Notation}
\begin{itemize}
    \item $A_1(\Phi)$: the closure of the convex hull of $\Phi$. Specifically, $A_1(\Phi) = \{g : g = \sum_i
c_i \phi_i, \; \phi_i \in \Phi, \; \sum_i|c_i| \le 1\}$
  \item $\supp(a)$: the support of $a\in\mathbb{R}^d$ is the index set where
the elements of $a$ are nonzero

  \item $|\Lambda|$: the cardinality of the set $\Lambda$

  \item $\Phi_\Lambda$: the sub-dictionary of $\Phi$ with the indices of atoms
restricted to the index set $\Lambda$

  \item $a_\Lambda$: the sub-signal (in $\mathbb{R}^{|\Lambda|}$) of $a\in
    \mathbb{R}^d$ with indices restricted to $\Lambda$
  \item $a_{\text{min}}$: the nonzero element of $a$ with the least magnitude
\end{itemize}

\subsection{Preliminaries}
As mentioned above, there are two types of metrics that are frequently used in the CS
literature, the coherence indices and the RIC. The use of coherence indices can be traced back to~\cite{DH},
where Donoho and Huo used the mutual coherence to describe the
equivalence of the $\ell_0$ minimization and $\ell_1$ minimization.
\begin{defn}\label{def:mutualcoherence}
  The \emph{mutual coherence} $M(\Phi)$ of a matrix $\Phi$ is defined by
  \begin{align*}
    M(\Phi) := \max_{\substack{\phi_i, \phi_j \in \Phi \\ i \neq
        j}} | \langle \phi_i, \phi_j  \rangle |,
  \end{align*}
  where $\langle \cdot, \cdot \rangle$ represents the usual inner product.
\end{defn}
\noindent They showed that~\cite{DH} if $k < (1+M^{-1})/2$, then the $\ell_1$
minimization problem  has a unique solution and is equivalent to
the $\ell_0$ minimization problem. Further results using the mutual
coherence for $\ell_1$ minimization can be found
in~\cite{MR1929464,MR1963681,MR2045813}. Interestingly, OMP shares the
same bound as the $\ell_1$ minimization problem.  It has been shown in~\cite{DET2,DET}
that if $k < (1+M^{-1})/2$, then OMP can recover the true support of the
ideal signal in $k$ iterations in presence of noise, and get exact
recovery of the signal in noiseless case. Moreover, this bound is
known to be sharp.

The other metric, the RIC, was introduced by Candes
and Tao in \cite{Candes2005:LP}.
\begin{defn}[Restricted Isometry Property]
  Let $\Sigma_k$ be the set of $k$-sparse vectors $\Sigma_k = \{u\in\mathbb{R}^d: \|u\|_0 \le k\}$. A matrix $\Phi$ satisfies the \emph{restricted isometry property}
  of order $k$ with the \emph{restricted isometry constant (RIC)} $\delta_k$
  if $\delta_k$ is the smallest constant such that
  \begin{align*}
    (1-\delta_k)\|v\|_2^2 \le \|\Phi v\|_2^2 \le (1+\delta_k)\|v\|_2^2
  \end{align*}
  holds for all $v \in \Sigma_k$.
\end{defn}

% \section{Background}




It is easy to see that the RIC $\delta_k$ increases with $k$ since
$\Sigma_k \subset \Sigma_{k+1}$. Candes shows in \cite{Candes:08} if
$\delta_{2k} < \sqrt{2} - 1$, then $\ell_1$ minimization is equivalent to
$\ell_0$ minimization. Better bounds have been developed
\cite{Foucart2009395, Foucart201097, 5290058, 5550400, Mo2011460} and the most
recent result is $\delta_{2k} < 0.4931$
\cite{Mo2011460}. In contrast to
$\ell_1$ minimization, the conventional metric for a sensing matrix in using greedy
algorithms is usually chosen to be the coherence indices (see for instance
\cite{1337101,DET,5361489}). Recently, researchers have started to investigate the
performance of OMP using the RIC. Davenport and
Wakin~\cite{5550495} have proved that $\delta_{k+1} <
\frac{1}{3\sqrt{k}}$ is sufficient for OMP to recover any $k$-sparse
signal in $k$ iterations. Further improvements have
been reported in \cite{HuangZhu:11, 6092487, 6213142, MoShen:12}. In
particular, \my{Wang and Shim~\cite{6213142}\footnote{\my{In the construction
  of the bound in this paper, the condition was strengthened from
  $\sqrt{k}\delta_{k+1} + \delta_k < 1$ for the first iteration of OMP
  to
  $\delta_{k+1} < \frac{1}{\sqrt{k}+1}$ for the subsequent iterations
  and the main result.}} and} Mo
and Shen~\cite{MoShen:12} have improved the
bound to $\delta_{k+1} < \frac{1}{\sqrt{k}+1}$, and have also given an
example that OMP fails after $k$ iterations when $\delta_{k+1} = \frac{1}{\sqrt{k}}$, as
was conjectured by Dai and Milenkovic in
\cite{4839056}. Zhang\cite{Zhang:2011} has also given a bound
$\delta_{31k} < 1/3$ for OMP to recover a $k$-sparse signal in more
than $k$ iterations. Loosely
speaking, as discussed in~\cite{DuarteEldar:2011}, Zhang's result requires fewer measurements when $k$ is large. However, when $k$ is small, his result is
worse. In addition, Zhang's algorithm requires more than $k$
iterations, and cannot recover the true support of the ideal
sparse signal% when noise is present
.

\my{Whilst coherence measures and the RIC have been used in many studies,
the two metrics have generally been considered
independently. In~\cite{YangdeHoog:2014}, the global 2-coherence was
introduced as a means of providing a bridge between them. }
% While there have been substantial efforts to study these two metrics
% independently, a useful bridge connecting them was missing. One of these
% bridges has been established in~\cite{YangdeHoog:2014}. Let us 
% first introduce the \emph{global 2-coherence}, $\nu_k(\Phi)$ for a given
% dictionary $\Phi$, as defined in~\cite{YangdeHoog:2014}.

\begin{defn}\label{def:newcoherence}
  Denote $[d]$ the index set $\{1,2,\ldots,d\}$. The \emph{global 2-coherence} of a dictionary $\Phi \in \mathbb{R}^{n\times d}$ is defined as
  \begin{equation*}\label{eqn:newcoherence}
    \nu_k(\Phi):=
    \max_{i\in[d]}\max_{\substack{\Lambda\subseteq[d]\setminus\{i\} \\ |\Lambda| \le k}}
    \left( \sum_{j\in\Lambda} \langle \phi_i,\phi_j \rangle^2
    \right)^{1/2},
  \end{equation*}
  where $\phi_i$, $\phi_j$ are atoms from the dictionary $\Phi$.
\end{defn}
\noindent Note that the global 2-coherence $\nu_k (\Phi)$
defined in Definition~\ref{def:newcoherence} is more
general than the mutual coherence defined in
Definition~\ref{def:mutualcoherence}. In fact, when $k=1$, the global
2-coherence defined in Definition~\ref{def:newcoherence} is
exactly the mutual coherence. It is also
more general than the ``local'' 2-coherence function defined
in~\cite{5361489}. 
\my{
  The intuition behind this definition can be seen from the following. For greedy methods which add elements by examining inner products
  of residuals, we require sharp bounds for $|\langle \Phi a, \phi_i
  \rangle|$ where $\|a\|_0 = k < n$ and $\phi_i$ is the $i$th column of
  $\Phi$. Specifically, we need an upper bound for $|\langle \Phi a, \phi_i
  \rangle|$ when $i \notin \Lambda$ and a lower bound for $|\langle \Phi a, \phi_i
  \rangle|$ when $i \in \Lambda$, where $\Lambda = \text{supp}(a)$. Such bounds have been derived
  in~\cite{YangdeHoog:2014}, namely
  \begin{align}
    &\max_{\phi_i, i \notin \Lambda} |\langle \Phi a, \phi_i
    \rangle| \le \nu_k \|a\|_2,  \notag \\
    &\max_{\phi_i, i \in \Lambda} |\langle \Phi a, \phi_i
    \rangle| \ge \frac{(1-\delta_k)\|a\|_2}{\sqrt{k}}. \label{eqn:inner_product_upper_bound}
  \end{align}
  It is straightforward to show that the first bound is sharp in the
  sense that for every sampling matrix $\Phi$ there is a $k$-sparse
  vector $a$ such that the equality holds. Thus, the global 2-coherence is
  a natural metric to use for the analysis of greedy algorithms. Note
  however that the second inequality is not sharp for all choices of
  sampling matrix $\Phi$. We could have used the metric
  \begin{align*}
    \omega_k(\Phi) = \min_{\|x\|_0 = k} \max_{\substack{\phi_i, 
        i\in \Lambda}} \frac{|\langle \Phi x, \phi_i
    \rangle|}{\|x\|_2},
\end{align*}
\mymy{which would replace Equation~\eqref{eqn:inner_product_upper_bound}
with the bound
\begin{align*}
  \max_{\phi_i, i \in \Lambda} |\langle \Phi a, \phi_i
    \rangle| \ge \omega_k(\Phi) \|a\|_2,
  \end{align*}
 which is sharp in the sense that for every sampling matrix $\Phi$
 there is a $k$-sparse vector $a$ such that the equality
 holds. However, we have}
opted to work with the
RIC as it is a more familiar measure and leads to estimates that are
nearly as good. Thus both the RIC and the global 2-coherence are
natural metrics to use in the analysis of greedy algorithms. Note that
the metric $\omega_k(\Phi)$ can be written using operator norm as (see
appendix for details)
\begin{align}\label{eqn:omega}
  \omega_k(\Phi) = \min_{\substack{\Lambda \subset [d] \\ |\Lambda| = k}}
  \frac{1}{\|(\Phi_\Lambda^T \Phi_\Lambda)^{-1}\|_{\infty, 2}},
\end{align}
where $\Phi_\Lambda$ denotes the sub-dictionary of $\Phi$ with indices of atoms
restricted to the index set $\Lambda$.
}\mymy{The mixed norm $\|\cdot\|_{\alpha,\beta}$ here is defined as
  \begin{align*}
    \|A\|_{\alpha,\beta} = \max_{x\neq 0} \frac{\|A\|_\beta}{\|x\|_\alpha}.
\end{align*}
}

\my{The global 2-coherence can also be written as
  \begin{align}
    \nu_k(\Phi) = \max_{\substack{\Lambda\subseteq[d] \\ |\Lambda| \le
        k+1}} \| \Phi_\Lambda^T \Phi_\Lambda - I \|_{\infty, 2},
    \label{eqn:2coherence}
  \end{align}
It is no more complicated than
the RIC, which can be expressed as
\begin{align}
  \delta_k = \max_{\substack{\Lambda\subseteq[d] \\ |\Lambda| \le k}}
  \| \Phi_\Lambda^T \Phi_\Lambda - I \|_{2, 2}.
  \label{eqn:ric}
\end{align}
In fact, from an algorithmic point of view, the global 2-coherence is more useful in
practice as it can be calculated in polynomial time.

Equations~\eqref{eqn:2coherence}~and~\eqref{eqn:ric} are used in the
proof of the following proposition (see~\cite{YangdeHoog:2014} for details).}

\begin{pro}\label{pro:relationship}
    For $k \ge 1$, 
    \begin{equation}\label{eqn:relationship}
        M \le \nu_{k} \le  \delta_{k+1} \le \sqrt{k}\nu_{k} \le kM.
    \end{equation}
  \end{pro}
  \noindent This proposition provides the upper and lower bounds for both the mutual
  coherence $M$ and the RIC $\delta_k$ in terms of the global
  2-coherence $\nu_k$, which establishes the bridge between them. It
  connects the two once independent metrics for greedy algorithms
  together. Moreover, by applying inequalities~\eqref{eqn:relationship}, the authors
  improved the bound on the RIC for OMP to $\delta_k + \sqrt{k}\delta_{k+1}<1$.

Next, in addition to
Proposition~\ref{pro:relationship}, we establish in this paper the relationship among the global 2-coherence $\nu_k$, the cumulative coherence $\mu_{1,k}$ defined in~\cite{1337101},
and the RIC $\delta_k$.

\begin{pro}\label{pro:relationship_new}
    For $k \ge 1$, we have
    \begin{equation*}
        \delta_{k+1} \le \mu_{1,k} \le \sqrt{k}\nu_{k}.
    \end{equation*}
\end{pro}

\begin{proof}
  The inequality $\delta_{k+1} \le \mu_{1,k}$ has been established in
  Proposition 2.10 in~\cite{Rauhut:10}. We next show $\mu_{1,k} \le
  \sqrt{k}\nu_{k}$ for all positive integer $k$.
  \begin{align*}
    \mu_{1,k}
    &=
     \max_{i\in[d]}\max_{\substack{\Lambda\subseteq[d]\setminus\{i\}
         \\ |\Lambda| \le k}} \sum_{j\in\Lambda} |\langle \phi_i,
     \phi_j \rangle| \\
     &\le
      \max_{i\in[d]}\max_{\substack{\Lambda\subseteq[d]\setminus\{i\}
          \\ |\Lambda| \le m}} \left( \sum_{j\in\Lambda} \langle \phi_i,\phi_j \rangle^2
      \right)^{1/2} \cdot \sqrt{k} \\
      &=
      \sqrt{k}\nu_k.
    \end{align*}
  \end{proof}
\noindent  Notice that from the above relations, we see clearly that the cumulative
coherence can only bound the restricted isometry constant from above,
which provides another motivation for introducing the global 2-coherence.


\section{Main Results}\label{sec:main}
In this section, we start the analysis of the recovery properties of
OMPT with the noiseless case, and compare them with the
state-of-art results. We then generalize the results to the case where
a measurement signal is contaminated by a perturbation. A convergence
analysis of OMPT is also given, which can be extended to the more general
Hilbert space. To make the paper more readable, the detailed
proofs of the main results are relegated to the Appendix.


Let us first introduce the OMPT algorithm. This is a thresholding type
modification of OMP and weak OMP (WOMP). It replaces
the expensive greedy step in OMP and WOMP with a thresholding
step. Details are presented in Algorithm~\ref{alg:ompt}, where
$\Phi_{\Lambda_s}$ denotes the sub-dictionary of $\Phi$ with atoms
restricted to the index set $\Lambda_s$ from the $s$-th iteration, and $\hat{a}_{\Lambda_k}$
denotes $\hat{a}$ restricted to the support set $\Lambda_k$ after $k$
iterations. \myIII{Note that in the thresholding step (step 4 in
  Algorithm~\ref{alg:ompt}), unlike some multi-index thresholding
  algorithms such as StOMP~\cite{6145475}, only the first index satisfying the
  thresholding condition is picked from a randomly permuted index set.} An
initial study of this algorithm in Hilbert space was presented
in~\cite{Yang:2011:GAA:2338237}. For the case of Banach space, a
similar version of the algorithm was studied in~\cite{Temlyakov:08}
(see also \cite{T9} and \cite{Temlyakov:11}). However, as far as we
are aware, the present paper provides  the first analysis of the
performance of this algorithm for sparse signal recovery in
CS using different coherence indices and the restricted isometry
constant.



\begin{algorithm}
  \caption{Orthogonal Matching Pursuit with Thresholding (OMPT)}
  \begin{algorithmic}[1]
    \STATE\textbf{Input:} threshold $t$, dictionary $\Phi$,
    signal $f$.
    \STATE\textbf{Initialization:} $r_0 := f$, $x_0:=0$, 
    $\Lambda_0:=\emptyset$, $s:=0$.
    \WHILE {$\|r_s\|_2 > t \|f\|_2$}
      \STATE Find an index $i$ such that $$|\langle r_s,\phi_i\rangle|
      \ge t\|r_s\|_2;$$
      \STATE Update the support: $$\Lambda_{s+1} = \Lambda_s \cup \{i\};$$
      \STATE Update the estimate: $$x_{s+1} = \argmin_z \|f - \Phi_{\Lambda_{s+1}} z\|_2;$$
      \STATE Update the residual: $$r_{s+1} = f - \Phi_{\Lambda_{s+1}} x_{s+1};$$
      \STATE $s = s+1$;
    \ENDWHILE
    \STATE \textbf{Output:} If the algorithm is stopped after $k$
    iterations, then the output estimate $\hat{a}$ of $a$ is
    $\hat{a}_{\Lambda_k} = x_k$ and $\hat{a}_{\Lambda_k^C} = 0$.
  \end{algorithmic}
  \label{alg:ompt}
\end{algorithm}


First we study the recovery properties of the OMPT algorithm. We start
with the ideal noiseless case where the measurement signal is
obtained by encoding a sparse signal. Specifically, let
$\Lambda\subset [d]$ with $|\Lambda| = k$. We consider a measurement
$f = \Phi a$, where $\Phi \in
\mathbb{R}^{n\times d}$ and $a\in\mathbb{R}^d$ with $\supp(a) = \Lambda$.
We have the following results.

\begin{thm}\label{thm:ompt_noiseless}
  Let $f = \Phi a$ with $\|a\|_0 = k$. If
  \begin{align}
    \delta_k + \sqrt{k}\nu_k < 1 \label{eqn:thm_ompt_bound}
  \end{align}
  and
  \begin{align}
    \frac{\nu_k}{\sqrt{1-\delta_k}} < t \le
    \frac{\sqrt{1-\delta_k}}{\sqrt{k}}, \label{eqn:ompt_thm_condition}
  \end{align}
  then $a$ is the unique sparsest representation of $f$ and moreover,
  OMPT recovers $a$ exactly in $k$ iterations.
\end{thm}
\my{\noindent This result for noiseless recovery property of OMPT involves the
  global 2-coherence and the RIC. This is the most accurate bound in
  the paper and is the basis for the derivation of simpler bounds
  given in Corollary~\ref{cor:ompt}. As the proof of this theorem is a special case of
Theorem~\ref{thm:ompt_noisy}, we refer the reader to the proof of Theorem~\ref{thm:ompt_noisy}, which is given in the appendix.}

% \my{\noindent This is the best result we are able the get in this
%   paper for the noiseless
% recovery property of OMPT, which is a hybrid of the global-2
% coherence and the RIC. Everything else follows from this result and Proposition~\ref{pro:relationship} and Proposition~\ref{pro:relationship_new}.
% The proof of this theorem is a special case of
% Theorem~\ref{thm:ompt_noisy} and is therefore not given in the
% appendices.}



% \section{Discussion}\label{sec:discussion}
Notice that the condition~\eqref{eqn:ompt_thm_condition} on the
threshold $t$ requires the
bound~\eqref{eqn:thm_ompt_bound} as a sufficient
condition. Next we will examine this bound and compare it with the
corresponding bound for OMP by exploring the relationships among
different coherence indices and the restricted isometry
constant. 


Now by applying Proposition~\ref{pro:relationship} and Proposition~\ref{pro:relationship_new} to
Theorem~\ref{thm:ompt_noiseless}, we obtain the following corollary.

\begin{cor}\label{cor:ompt}
  Let $f = \Phi a$ with $\|a\|_0 = k$ ($k \ge 2$). If any of the following four
  conditions is satisfied:
  \begin{enumerate}[i)]
    \item
      \begin{align}
        \delta_k + \sqrt{k} \delta_{k+1} <
        1 \label{eqn:ompt_cor_condition_delta} 
      \end{align}
      and
      \begin{align*}
        \frac{\delta_{k+1}}{\sqrt{1-\delta_k}} < t \le
        \frac{\sqrt{1-\delta_k}}{\sqrt{k}},
      \end{align*}
    \item
      \begin{align*}
        \nu_k\sqrt{k} + \nu_{k-1}\sqrt{k-1} < 1 % \label{eqn:ompt_cor_condition_nu}
      \end{align*}
      and
      \begin{align*}
        \frac{\nu_k}{\sqrt{1-\nu_{k-1}\sqrt{k-1}}} < t \le
        \frac{\sqrt{1-\nu_{k-1}\sqrt{k-1}}}{\sqrt{k}}, \notag
      \end{align*}
    \item
      \begin{align*}
        \mu_{1,k-1} + \sqrt{k}\mu_{1,k} < 1 % \label{eqn:ompt_cor_condition_mu}
      \end{align*}
      and
      \begin{align*}
        \frac{\mu_{1,k}}{\sqrt{1-\mu_{1,k-1}}} < t \le
        \frac{\sqrt{1-\mu_{1,k-1}}}{\sqrt{k}}, \notag
      \end{align*}
    \item
      \begin{align}
        M < \frac{1}{2k-1} \label{eqn:ompt_cor_condition_M}
      \end{align}
      and
      \begin{align}
        \frac{\sqrt{k}M}{\sqrt{1-(k-1)M}} < t \le
        \frac{\sqrt{1-(k-1)M}}{\sqrt{k}}, \label{eqn:ompt_cor_condition_t}
      \end{align}
    \end{enumerate}
  then $a$ is the unique sparsest representation of $f$ and moreover,
  OMPT recovers $a$ exactly in $k$ iterations.
\end{cor}

As we can see from the above corollary, although we are replacing the most difficult
  (expensive) step of OMP,
  namely the greedy step, by a very simple thresholding step, thus
  making it substantially more efficient, there is no performance degrading. The
  bound~\eqref{eqn:ompt_cor_condition_delta} on the restricted
  isometry constant $\delta_k$ is exactly the same as
  the bound in\cite[Corollary 3.3]{YangdeHoog:2014}
  for OMP. The bound~\eqref{eqn:ompt_cor_condition_M} on
  mutual coherence $M$ also coincides with the
  best known bound~\cite{Temlyakov:11}. Notice that the
  bound~\eqref{eqn:ompt_cor_condition_delta} gives an improved bound
  on the restricted isometry constant compared to the bound obtained
  in\cite{6213142,MoShen:12} for exact recovery of a $k$-sparse signal in
  $k$ iterations, where the bound was $\delta_{k+1} < \frac{1}{\sqrt{k}+1}$.



Theorem~\ref{thm:ompt_noiseless} can be generalized to the
noisy case. Specifically, Let $\Lambda \subset
[d]$ with $|\Lambda| = k$. We consider a measurement $f = \Phi
a + w$, where $a\in\mathbb{R}^d$ with $\supp(a) = \Lambda$ and
$\|w\|_2 \le \epsilon$. We will inspect the recovery performance of OMPT
after $k$ iterations. Denote by $a_{\text{min}}$ the nonzero entry of the
sparse signal $a$ with the least
  magnitude. The following two lemmas will be needed.

\begin{lem}\label{lem:t_lowerbound_noisy}
  Consider the residual at the $s$-th iteration of OMPT $r_s = \Phi
  a_s + w_s$.
  If
  % \begin{align}
  %   t >
  %   \frac{\nu_k\|a\|_\infty+\epsilon}{\sqrt{1-\delta_k}\|a\|_\infty-\epsilon}, \label{eqn:t_lowerbound_noisy}
  % \end{align}
  \begin{align}
    t >
    \frac{\nu_k |a_{\emph{min}}|+\epsilon}{\sqrt{1-\delta_k}
      |a_{\emph{min}}|-\epsilon}, \label{eqn:t_lowerbound_noisy}
  \end{align}
  then
  \begin{align*}
    \max_{i \in [d]\setminus\Lambda} |\langle r_s,\phi_i \rangle| < t \|r_s\|_2.
  \end{align*}
\end{lem}



\begin{lem}\label{lem:t_upperbound_noisy}
 Consider the residual at the $s$-th iteration of OMPT $r_s = \Phi
  a_s + w_s$. Given
  \begin{align}
    t \le \frac{(1-\delta_k) |a_{\emph{min}}| -
      \epsilon}{\sqrt{k(1-\delta_k)} |a_{\emph{min}}|+\epsilon}, \label{eqn:t_upperbound_noisy}
  \end{align}
  we have
  \begin{align*}
    \max_{i \in \Lambda} |\langle r_s,\phi_i \rangle| \ge t \|r_s\|_2.
  \end{align*}
\end{lem}



\begin{thm}\label{thm:ompt_noisy}
   Denote by $\hat{a}_{\emph{ompt}}$ the recovered signal from
  $f$ by OMPT after $k$ iterations. If
  \begin{align}
    \delta_k + \sqrt{k}\nu_k < 1 \label{eqn:thm_ompt_bound1_noisy}
  \end{align}
  and the noise level obeys
  % \begin{align}
  %   |a_{\text{min}}| > \frac{\epsilon\Big((1-\delta_k) +
  %     k\sqrt{k(1+\delta_k)}\Big)}{(1-\delta_k) \sqrt{k(1+\delta_k)} - k\nu_k\sqrt{1+\delta_k}},
  % \end{align}
  % and the threshold $t$ satisfies
  % \begin{align}
  %   &\frac{\nu_k}{\sqrt{1-\delta_k}} \left( 1 +
  %     \frac{\epsilon \sqrt{k}}{|a_{\text{min}}| \nu_k} \right) < t \notag\\
  %   &\le \frac{\sqrt{1-\delta_k}}{\sqrt{k}} \left( 1 -
  %     \frac{\epsilon}{|a_{\text{min}}| \sqrt{k(1+\delta_k)}} \right),
  % \end{align}
  \begin{align}
    \epsilon < \frac{\sqrt{1-\delta_k} (1-\delta_k -
      \sqrt{k}\nu_k)}{(\sqrt{k}+1)\sqrt{1-\delta_k} +      
       (1-\delta_k) + \nu_k}|a_{\emph{min}}|, \label{eqn:thm_ompt_bound2_noisy}
    % |a_{\text{min}}| > \frac{(\sqrt{k}+1)\sqrt{1-\delta_k} +
    %   (1-\delta_k) + \sqrt{k}\nu_k}{\sqrt{1-\delta_k} (1-\delta_k -
    %   \sqrt{k}\nu_k)} \epsilon, \label{eqn:thm_ompt_bound2_noisy}
  \end{align}
  then there exists threshold $t$ satisfying conditions
  \eqref{eqn:t_lowerbound_noisy} and \eqref{eqn:t_upperbound_noisy}.
  Moreover, we have
  \begin{enumerate}[a)]
        \item $\hat{a}_{\emph{ompt}}$ has the correct sparsity pattern, that is
            \begin{equation*}
                \supp(\hat{a}_{\emph{ompt}}) = \supp(a);
            \end{equation*}
         \item $\hat{a}_{\emph{ompt}}$ approximates the ideal
           noiseless representation and
             \begin{equation}
                 \|\hat{a}_{\emph{ompt}} - a\|_2^2 \leq
                 \frac{\epsilon^2}{1-\delta_k}. \label{eqn:thm_ompt_errorbound_noisy}
             \end{equation}
    \end{enumerate}
\end{thm}



Theorem~\ref{thm:ompt_noisy} basically says that, if the minimal nonzero
entry of the ideal noiseless sparse signal is large enough
compared to the noise level, then the correct support of the sparse
signal can be recovered exactly in $k$ iterations, and moreover, the error can be bounded by \eqref{eqn:thm_ompt_errorbound_noisy}. 

Next we study the convergence of the OMPT algorithm in presence of noise.

% \begin{defn}
%   Given a dictionary $\mathcal{D}$, the convex hull of $\mathcal{D}$
%   is defined as $A_1(\mathcal{D}) = \{g: g = \sum_i c_i \phi_i, \;
%   \phi_i \in \mathcal{D}, \; \sum_i |c_i| \le 1\}$.
% \end{defn}


\begin{thm}\label{thm:ompt_convergence}
  Given a dictionary $\Phi$, take $\epsilon \ge 0$ and $f, f^\epsilon
  \in \mathbb{R}^n$ such that
  \begin{align*}
    \|f - f^\epsilon\| \le \epsilon, \quad\quad f^\epsilon /
    C(\epsilon) \in A_1(\Phi)
  \end{align*}
  with some constant $C(\epsilon) > 0$. Then OMPT stops after $m \le 
  \ln t^2 / \ln(1 - t^2)$ iterations with
  \begin{align*}
    \|r_m\| \le \epsilon + t C(\epsilon).
  \end{align*}
\end{thm}

\begin{rmk}
Note that from the proof of Theorem~\ref{thm:ompt_convergence} (see
Appendix), it is clear that the residual term $r_m$ converges in an exponential rate. In addition, the
results in Theorem~\ref{thm:ompt_convergence} can be easily extended
to any Hilbert space.
\end{rmk}
\my{
\begin{rmk}
  Also note that when we choose $t^2$ to be close to
  $1/k$ as in Lemma~\ref{lem:t_upperbound_noisy}, the bound $\ln t^2 / \ln (1-t^2)$ for the number of
  iterations $m$ is roughly $k \ln k$. This can be seen by using the fact that $(1 - 1/k)^k$ is approximately $1/e$.
\end{rmk}
}

%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}


% Note that IEEE does not put floats in the very first column - or typically
% anywhere on the first page for that matter. Also, in-text middle ("here")
% positioning is not used. Most IEEE journals use top floats exclusively.
% Note that, LaTeX2e, unlike IEEE journals, places footnotes above bottom
% floats. This can be corrected via the \fnbelowfloat command of the
% stfloats package.

\mymy{
\section{Simulations}
In this section, we present simulations that compare the
reconstruction performance and the complexity of OMPT with
OMP. For this purpose, we use similar setup to that given in~\cite{DET}. Specifically, we work
with a dictionary $\Phi = [I, F] \in \mathbb{R}^{128 \times 256}$, concatenating a standard basis and a
Fourier basis for signals of length $128$ together. The sparse signals we
test are obtained by randomly choosing locations for
nonzero entries, and then assigning values from the uniform
distribution to these locations. We perform 1000 trials for each of such
sparse signals generated with certain sparsity level.

We first examine the reconstruction performance of OMPT and compare it
with that of OMP. For simplicity, we only consider the metric
using mutual coherence $M$. In particular, we choose for OMPT the
thresholding parameter $t = \sqrt{M} = 1/\sqrt{128}$, which satisfies the
condition~\eqref{eqn:ompt_cor_condition_t} for sparsity $k = 1,
\ldots, 6$ satisfying
condition~\eqref{eqn:ompt_cor_condition_M}. Figure~\ref{fig:performance}
shows the reconstruction performance of OMPT under the above settings
and that of its counter part OMP. The $x$-axis is the sparsity level and the
$y$-axis is the expected value of success. We see from the figure that OMPT has
similar performance as OMP. In particular, OMPT performs better than
OMP when sparsity $k$ is less than 30. Moreover, OMPT does not fail
when $k$ is no more than 20.

\begin{figure}[ht!]
  \centering
  \includegraphics[scale=.4]{performance.pdf}
  \caption{Average reconstruction performance of OMPT and OMP for
    sparse signals of length 256 in
    1000 trials.}
  \label{fig:performance}
\end{figure}

We next compare the complexity of OMPT and OMP in terms of number of
inner products needed. For OMP, one can actually calculate the number
of inner products, which equals $k(2d-k+1)/2$. It increases as
sparsity $k$ increases, as shown in Figure~\ref{fig:complexity}. In
contrast, we count the number of inner products performed by OMPT for
1000 trials. The average is shown in
Figure~\ref{fig:complexity}. As one can see, it stays flat as $k$
increases and is significantly less than the number of inner products needed
for OMP.


\begin{figure}[ht!]
  \centering
  \includegraphics[scale=.4]{complexity.pdf}
  \caption{Average number of inner products performed by OMPT and OMP
    in 1000 trials.}
  \label{fig:complexity}
\end{figure}

}

\section{Conclusion}
In this paper, we have analyzed a less greedy algorithm, orthogonal matching pursuit with
thresholding and its performance for reconstructing sparse signals,
for both noisy and noiseless cases. It
replaces the expensive greedy step in orthogonal matching pursuit with
a thresholding step, making it a potentially  more attractive option
in practice. By analysing different metrics for the sampling matrix
such as the RIC, mutual coherence and global 2-coherence, we showed
that although the expensive greedy step is replaced, this simplified
algorithm has the same recovery performance as orthogonal matching
pursuit for sparse signal reconstruction.




% if have a single appendix:
%\appendix[Proof of the Zonklar Equations]
% or
%\appendix  % for no appendix heading
% do not use \section anymore after \appendix, only \section*
% is possibly needed

% use appendices with more than one appendix
% then use \section to start each appendix
% you must declare a \section before using any
% \subsection or using \label (\appendices by itself
% starts a section numbered zero.)
%


% \appendices
% \section{Proof of the First Zonklar Equation}
% Appendix one text goes here.

% % you can choose not to have a title for an appendix
% % if you want by leaving the argument blank
% \section{}
% Appendix two text goes here.

\appendices

\section{Proof of expression~\eqref{eqn:omega}}
\begin{proof}
  \begin{align*}
    \max_{\phi_i, i\in S} \frac{|\langle \Phi x, \phi_i
    \rangle|}{\|x\|_2}
    &=
    \frac{\|\Phi_S^T \Phi_S x_S\|_\infty}{\|x_S\|_2} \\
    &=
    \frac{\|\Phi_S^T \Phi_S x_S\|_\infty}{\|(\Phi_S^T
      \Phi_S)^{-1}\Phi_S^T \Phi_S x_S\|_2} \\
    &\ge
    \frac{1}{\|(\Phi_S^T \Phi_S)^{-1}\|_{\infty, 2}}.
  \end{align*}
  Therefore,
  \begin{align*}
    \omega_k(\Phi) = \min_{\substack{S \subset [d] \\ |S|=k}}
    \frac{1}{\|(\Phi_S^T \Phi_S)^{-1}\|_{\infty, 2}}.
  \end{align*}
\end{proof}


\section{Proof of Theorem~\ref{thm:ompt_noisy}}

The proof of Lemma~\ref{lem:t_lowerbound_noisy}
and Lemma~\ref{lem:t_upperbound_noisy} will need the following lemma.

\begin{lem}\label{lem:bounds_noisy}
  Let $\Lambda \subset [d]$ with $|\Lambda| = k$. Let $f
  = \Phi a + w$ with $\supp(a) = \Lambda$ and $\|w\|_2 \le
  \epsilon$. In addition, assume that there exits $\Omega \subseteq
  \Lambda$ with $|\Omega| = m$, such that
  \begin{align*}
    \langle \Phi a, \phi_i \rangle = 0, \mbox{ for $i\in \Lambda \setminus
      \Omega$}.
  \end{align*}
  Then
  \begin{align*}
    \max_{i \in [d]\setminus\Lambda} |\langle f,\phi_i \rangle|
    &\le
    \nu_k \|a\|_2 + \epsilon, \\
    \max_{i \in \Lambda} |\langle f,\phi_i \rangle|
    &\ge
    \frac{\sqrt{1-\delta_k}}{\sqrt{m}}  \|\Phi a\|_2 - \epsilon.
  \end{align*}
\end{lem}

\begin{proof}
  For $i \in [d]\setminus\Lambda$, we have
  \begin{align*}
    |\langle f,\phi_i \rangle|
    &=
    | \langle \Phi a + w, \phi_i \rangle| \\
    &\le
   |\langle \Phi a,\phi_i \rangle| + |\langle w,\phi_i \rangle|\\
   &\le
   \left| \sum_{j\in\Lambda} a_j \langle \phi_j, \phi_i \rangle
   \right| + \|w\|_2 \|\phi_i\|_2\\
   &\le
   \|a\|_2 \left( \sum_{j\in\Lambda} |\langle \phi_j, \phi_i
     \rangle|^2 \right)^{\frac{1}{2}} + \epsilon\\
   &\le
   \nu_k \|a\|_2 + \epsilon.
 \end{align*}
	Taking maximum on both sides completes the proof of the first inequality.

	Now for $i \in \Lambda$, we have
        \begin{align*}
          \|\Phi a\|_2^2
          &=
          \langle \Phi a, \sum_{i\in\Lambda} a_i \phi_i \rangle \\
          &=
          \sum_{i\in\Lambda} a_i \langle \Phi a, \phi_i \rangle \\
          &=
          \sum_{i\in\Omega} a_i \langle \Phi a, \phi_i \rangle \\
          &\le
          \sum_{i \in \Omega} |a_i|\cdot |\langle \Phi a,\phi_i \rangle| \\
          &\le
          \sqrt{m} \|a\|_2 \max_{i \in \Lambda} |\langle \Phi a,\phi_i \rangle|.
        \end{align*}
        By the definition of the RIC $\delta_k$,
        \begin{align*}
          \max_{i \in \Lambda} |\langle \Phi a , \phi_i \rangle| \ge \frac{\sqrt{1-\delta_k}}{\sqrt{m}} \|\Phi a\|_2.
        \end{align*}
        Therefore,
	\begin{align*}
          \max_{i \in \Lambda} |\langle f,\phi_i \rangle|
          &=
          \max_{i \in \Lambda} |\langle \Phi a + w,\phi_i \rangle|  \\
          &\ge
          \max_{i \in \Lambda} |\langle \Phi a , \phi_i \rangle| -
          \max_{i \in \Lambda} |\langle w, \phi_i \rangle| \\
          &\ge
          \frac{\sqrt{1-\delta_k}}{\sqrt{m}} \|\Phi a\|_2 - \max_{i
            \in \Lambda} \|w\|_2 \|\phi_i\|_2 \\
          &\ge
          \frac{\sqrt{1-\delta_k}}{\sqrt{m}} \|\Phi a\|_2 - \epsilon.
        \end{align*}
        This completes the proof of the second inequality.
\end{proof}

Now we are ready to complete the proof of
Lemma~\ref{lem:t_lowerbound_noisy},
Lemma~\ref{lem:t_upperbound_noisy}, and Theorem~\ref{thm:ompt_noisy}.

\begin{proof}[Proof of Lemma~\ref{lem:t_lowerbound_noisy}]
  By using Lemma~\ref{lem:bounds_noisy}, assumption~\eqref{eqn:t_lowerbound_noisy}, and the fact that
  $\|a_s\|_2 \ge \sqrt{k-s} |a_{\text{min}}|$, it is easy to derive
  \begin{align*}
    \max_{i \in [d]\setminus\Lambda} |\langle r_s,\phi_i \rangle|
    &\le
    \nu_k \|a_s\|_2 + \epsilon \\
    &<
    t \left( \sqrt{1-\delta_k}\|a_s\|_2 - \epsilon \right) \\
    &\le
    t \left( \|\Phi a_s\|_2 -\epsilon \right) \\
    &\le
    t \|r_s\|_2.
  \end{align*}
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:t_upperbound_noisy}]
  By using Lemma~\ref{lem:bounds_noisy}, assumption~\eqref{eqn:t_upperbound_noisy}
  and the inequality
  \begin{align*}
    \sqrt{(k-s)(1-\delta_k)} |a_{\text{min}}| \le \sqrt{1-\delta_k}\|a\|_2 \le
    \|\Phi a\|_2
  \end{align*}
  we have
  \begin{align*}
    \max_{i \in \Lambda} |\langle r_s,\phi_i \rangle| 
    &\ge
    \frac{\sqrt{1-\delta_k}}{\sqrt{k-s}} \|\Phi a_s\|_2 - \epsilon \\
    &\ge
    t (\|\Phi a_s\|_2 + \epsilon) \\
    &\ge
    t \|r_s\|_2.
  \end{align*}
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:ompt_noisy}]
  First we show that $a_{\text{ompt}}$ has the correct support.

  We start with the first iteration. Combining conditions
  \eqref{eqn:thm_ompt_bound1_noisy} and
  \eqref{eqn:thm_ompt_bound2_noisy},
  Lemma~\ref{lem:t_lowerbound_noisy} and
  Lemma~\ref{lem:t_upperbound_noisy}, it is easy to see that OMPT is
  able to select and only select an atom $\phi_i$ with $i \in
  \Lambda$. Condition~\eqref{eqn:thm_ompt_bound1_noisy} and
  ~\eqref{eqn:thm_ompt_bound2_noisy} guarantees the existance of
  threshold $t$ satisfying Lemma~\ref{lem:t_lowerbound_noisy} and
  Lemma~\ref{lem:t_upperbound_noisy}. Lemma~\ref{lem:t_lowerbound_noisy}
  guarantees that OMPT will not choose any atom $\phi_i$ for $i \in
  [d]\setminus\Lambda$. While Lemma~\ref{lem:t_upperbound_noisy} guarantees that
  OMPT is able to choose atoms $\phi_i$ with $i \in \Lambda$.

  Next we argue that by repeatedly applying
  Lemma~\ref{lem:t_lowerbound_noisy} and
  Lemma~\ref{lem:t_upperbound_noisy}, we are
  able to correctly recover
  the support of $a$. In fact, in each iteration, we have the same
  situation as in the first iteration. In addition, the orthogonal
  projection step guarantees that the procedure will not repeat the
  atoms already chosen in previous iterations. Thus, all the correct
  support of the noiseless sparse signal $a$ can be recovered
  precisely after $k$ iterations.

 
  Next, we will prove the error
  bound~\eqref{eqn:thm_ompt_errorbound_noisy}. The proof follows the
  idea of Theorem 5.1 in \cite{DET}. Let $a_T$ denote $a$ restricted
  to its support. Similarly, let $\Phi_T$ denote the dictionary $\Phi$
  restricted to the support of $a$. The orthogonal projection step
  tells that OMPT solves for
  \begin{align*}
    \hat{a}_T = \argmin_{a_T} \| f - \Phi_T a_T\|_2 = \Phi_T^\dagger f
  \end{align*}
  where $\Phi_T^\dagger$ denotes the Moore-Penrose generalized inverse
  of $\Phi_T$. Then we have
  \begin{align*}
    \hat{a}_T
    &=
    \Phi_T^\dagger f \\
    &=
    \Phi_T^\dagger (\Phi a + w) \\
    &=
    \Phi_T^\dagger (\Phi_T a_T + w) \\
    &=
    a_T + \Phi_T^\dagger w.
  \end{align*}
  The term $\Phi_T^\dagger w$ denotes the reconstruction error. It can
  be bounded by
  \begin{align*}
    \|\hat{a}_{\text{ompt}} - a\|_2
    &=
    \|\hat{a}_T - a_T\|_2 \\
    &=
    \|\Phi_T^\dagger w\|_2 \\
    &\le
    \|\Phi_T^\dagger\|_2 \cdot \|w\|_2 \\
    &\le
    \epsilon/\sigma_{\text{min}}
  \end{align*}
  where we bound the norm of $\Phi_T^\dagger$ by the smallest singular
  value $\sigma_{\text{min}}$ of $\Phi$. Now by RIP, we have $\sigma_{\text{min}}^2
  \ge 1 - \delta_k$, and the error
  bound~\eqref{eqn:thm_ompt_errorbound_noisy} follows.
\end{proof}

  \section{Proof of Theorem~\ref{thm:ompt_convergence}}
  \begin{proof}[Proof of Theorem~\ref{thm:ompt_convergence}]
  If the stopping criteria $\|r_m\| \le t \|f\|$ is met, then the
  error estimation follow from the simple inequalities
  \begin{align*}
    \|f\| \le \|f - f^\epsilon\| + \|f^\epsilon\| \le \epsilon + C(\epsilon).
  \end{align*}
  Now assume the stopping criteria $|\langle r_m, \phi
  \rangle| < t \|r_m\|$ has been met for all $\phi \in \Phi$, and
  denote $G_m$ the approximant after $m$ iterations. Then
  \begin{align*}
    \|r_m\|^2
    &=
    \langle r_m, f - G_m \rangle = \langle r_m, f\rangle \\
    &=
    \langle r_m, f - f^\epsilon \rangle + \langle r_m, f^\epsilon
    \rangle \\
    &\le
    \|r_m\|\cdot \|f-f^\epsilon\| + C(\epsilon) \langle r_m,
    \sum_{\phi_i\in\Phi} a_i \phi_i \rangle \\
    &\le
    \epsilon \|r_m\| + C(\epsilon) \sum_{\phi_i\in\Phi} a_i
    \langle r_m, \phi_i \rangle \\
    &\le
    \epsilon \|r_m\| + t C(\epsilon) \|r_m\| \sum_{\phi_i\in\Phi} |a_i|\\
    &\le
    \epsilon \|r_m\| + t C(\epsilon)\|r_m\|.
  \end{align*}
  Therefore, we obtain the bound
  \begin{align*}
    \|r_m\| \le \epsilon + t C(\epsilon).
  \end{align*}
  Next, we prove the bound on the number of iterations. Suppose we are
  at the $k$-th iteration and have found $\phi_i$ such that
  \begin{align*}
    |\langle \phi_i, r_{k-1} \rangle| \ge t\|r_{k-1}\|.
  \end{align*}
  We now update the support
  \begin{align*}
    \Lambda_k = \Lambda_{k-1} \cup \{i\}.
  \end{align*}
  and calculate the new approximant
  \begin{align*}
    G_k = \Phi_{\Lambda_k} \cdot \arg\min_z \|f - \Phi_{\Lambda_k} z\|^2.
  \end{align*}
  Then
  \begin{align*}
    \|r_k\|^2
    &=
    \min_z \|f - \Phi_{\Lambda_k} z\|^2 \\
    &\le
    \|r_{k-1} - \langle r_{k-1}, \phi_i \rangle \phi_i \|^2 \\
    &=
    \|r_{k-1}\|^2 - \langle r_{k-1}, \phi_i \rangle^2 \\
    &\le
    \|r_{k-1}\|^2 - t^2 \|r_{k-1}\|^2 \\
    &=
    (1-t^2) \|r_{k-1}\|^2.
  \end{align*}
  Hence
  \begin{align*}
    \|r_k\| \le (1-t^2)^{\frac{1}{2}} \|r_{k-1}\|,
  \end{align*}
  which implies
  \begin{align*}
    \|r_k\| \le (1-t^2)^{\frac{k}{2}} \|f\|. % \label{eqn:ompt_convergence}
  \end{align*}
  
    From the stopping criteria $\|r_m\| \le t \|f\|$, we know that the
    algorithm will stop after $m$ iterations where $m$ is the smallest
    integer satisfying
    \begin{align*}
      \left( 1 - t^2 \right)^{\frac{k}{2}} \le t.
    \end{align*}
    This implies
    \begin{align*}
      m \le \frac{2\ln t}{\ln(1 - t^2)}.
    \end{align*}
  \end{proof}


% % use section* for acknowledgement
% \my{
% \section*{Acknowledgment}


% The authors would like to thank the anonymous reviewers for their valuable comments
% and suggestions.
% }

% Can use something like this to put references on a page
% by themselves when using endfloat and the captionsoff option.
\ifCLASSOPTIONcaptionsoff
  \newpage
\fi



% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
\bibliography{ga}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)

% \begin{thebibliography}{1}

% \bibitem{IEEEhowto:kopka}
% H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%   0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.

% \end{thebibliography}

% biography section
% 
% If you have an EPS/PDF photo (graphicx package needed) extra braces are
% needed around the contents of the optional argument to biography to prevent
% the LaTeX parser from getting confused when it sees the complicated
% \includegraphics command within an optional argument. (You could create
% your own custom macro containing the \includegraphics command to make things
% simpler here.)
%\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
% or if you just want to reserve a space for a photo:

% \begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mingrui}}]{Mingrui Yang}
% (M'11) is a Postdoctoral research
% fellow in the Autonomous System Lab of the Digital Productivity Flagship in CSIRO, Australia. He received
% his Ph.D. in Mathematics from the University
% of South Carolina, USA in 2011. He is interested in interdisciplinary researches in compressive sensing, sparse approximation, signal/image processing, greedy algorithms and
% nonlinear approximation, and their applications.
% He has published in high quality journals and conferences in mathematics and computer science, such as Advances in Computational
% Mathematics, ACM/IEEE IPSN, and ACM SenSys. He is a member of
% ACM and IEEE.
% \end{IEEEbiography}

% % if you will not have a photo at all:
% \begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{frank}}]{Frank de Hoog}
% is a CSIRO Fellow in the CSIRO Digital Productivity Flagship,
% Australia, a Fellow of Australian Mathematical Society, and
% a Fellow of Australian Academy of Technological Sciences and
% Engineering. He received his Ph.D. in Mathematics from the Australian National University in 1973 and has research interests in compressive sensing, the numerical solution of differential and integral equations, numerical transform techniques, computational linear algebra, solid mechanics, vibration of structures, stress analysis, heat and mass transfer and rheology.
% \end{IEEEbiography}

% \begin{IEEEbiography}{}
% Biography text here.
% \end{IEEEbiography}

% insert where needed to balance the two columns on the last page with
% biographies
%\newpage

% \begin{IEEEbiographynophoto}{Jane Doe}
% Biography text here.
% \end{IEEEbiographynophoto}

% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}



% that's all folks
\end{document}



TSP_version3_single_column.bbl
% Generated by IEEEtran.bst, version: 1.13 (2008/09/30)
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@samestyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand{\BIBentrySTDinterwordspacing}{\spaceskip=0pt\relax}
\providecommand{\BIBentryALTinterwordstretchfactor}{4}
\providecommand{\BIBentryALTinterwordspacing}{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand{\BIBforeignlanguage}[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}
\providecommand{\BIBdecl}{\relax}
\BIBdecl

\bibitem{CandesRombergTao:06}
E.~J. Candes, J.~Romberg, and T.~Tao, ``{Robust uncertainty principles: exact
  signal reconstruction from highly incomplete frequency information},''
  \emph{IEEE Trans. on Inf. Theory}, vol.~52, no.~2, pp. 489--509, 2006.

\bibitem{Candes2006:Optimal}
E.~J. Candes and T.~Tao, ``{Near-Optimal Signal Recovery From Random
  Projections: Universal Encoding Strategies?}'' \emph{IEEE Trans. on Inf.
  Theory}, vol.~52, no.~12, pp. 5406--5425, 2006.

\bibitem{Do}
D.~L. Donoho, ``Compressed sensing,'' \emph{IEEE Trans. Inform. Theory},
  vol.~52, no.~4, pp. 1289--1306, 2006.

\bibitem{Shannon1949:samplingtheorem}
C.~Shannon, ``{Communication in the presence of noise},'' \emph{Proceedings of
  the Institute of Radio Engineers (IRE)}, vol.~37, pp. 10--21, 1949.

\bibitem{Candes2005:LP}
E.~J. Candes and T.~Tao, ``{Decoding by linear programming},'' \emph{IEEE
  Trans. on Inf. Theory}, vol.~51, no.~12, pp. 4203--4215, 2005.

\bibitem{Candes:08}
E.~J. Candes, ``The restricted isometry property and its implications for
  compressed sensing,'' \emph{Comptes Rendus Mathematique}, vol. 346, no. 9-10,
  pp. 589 -- 592, 2008.

\bibitem{Foucart2009395}
S.~Foucart and M.-J. Lai, ``Sparsest solutions of underdetermined linear
  systems via $\ell_q$-minimization for $0<q\le 1$,'' \emph{Applied and
  Computational Harmonic Analysis}, vol.~26, no.~3, pp. 395 -- 407, 2009.

\bibitem{Foucart201097}
S.~Foucart, ``A note on guaranteed sparse recovery via $\ell_1$-minimization,''
  \emph{Applied and Computational Harmonic Analysis}, vol.~29, no.~1, pp. 97 --
  103, 2010.

\bibitem{5290058}
T.~Cai, L.~Wang, and G.~Xu, ``Shifting inequality and recovery of sparse
  signals,'' \emph{Signal Processing, IEEE Transactions on}, vol.~58, no.~3,
  pp. 1300--1308, 2010.

\bibitem{5550400}
------, ``New bounds for restricted isometry constants,'' \emph{Information
  Theory, IEEE Transactions on}, vol.~56, no.~9, pp. 4388--4394, 2010.

\bibitem{Mo2011460}
Q.~Mo and S.~Li, ``New bounds on the restricted isometry constant,''
  \emph{Applied and Computational Harmonic Analysis}, vol.~31, no.~3, pp. 460
  -- 468, 2011.

\bibitem{Gilbert:2003:AFO:644108.644149}
A.~C. Gilbert, S.~Muthukrishnan, and M.~J. Strauss, ``Approximation of
  functions over redundant dictionaries using coherence,'' in \emph{Proceedings
  of the fourteenth annual ACM-SIAM symposium on Discrete algorithms}, ser.
  SODA '03.\hskip 1em plus 0.5em minus 0.4em\relax Philadelphia, PA, USA:
  Society for Industrial and Applied Mathematics, 2003, pp. 243--252.

\bibitem{DET2}
D.~L. Donoho, M.~Elad, and V.~N. Temlyakov, ``Stable recovery of sparse
  overcomplete representations in the presence of noise,'' USC, Tech. Rep.
  04:06, 2004.

\bibitem{1337101}
J.~Tropp, ``Greed is good: algorithmic results for sparse approximation,''
  \emph{Information Theory, IEEE Transactions on}, vol.~50, no.~10, pp.
  2231--2242, 2004.

\bibitem{DET}
D.~L. Donoho, M.~Elad, and V.~N. Temlyakov, ``Stable recovery of sparse
  overcomplete representations in the presence of noise,'' \emph{IEEE Trans.
  Inform. Theory}, vol.~52, no.~1, pp. 6--18, 2006.

\bibitem{Needell2009301}
D.~Needell and J.~Tropp, ``Cosamp: Iterative signal recovery from incomplete
  and inaccurate samples,'' \emph{Applied and Computational Harmonic Analysis},
  vol.~26, no.~3, pp. 301 -- 321, 2009.

\bibitem{4839056}
W.~Dai and O.~Milenkovic, ``Subspace pursuit for compressive sensing signal
  reconstruction,'' \emph{Information Theory, IEEE Transactions on}, vol.~55,
  no.~5, pp. 2230--2249, 2009.

\bibitem{5419092}
D.~Needell and R.~Vershynin, ``Signal recovery from incomplete and inaccurate
  measurements via regularized orthogonal matching pursuit,'' \emph{Selected
  Topics in Signal Processing, IEEE Journal of}, vol.~4, no.~2, pp. 310--316,
  2010.

\bibitem{Blumensath2009265}
T.~Blumensath and M.~E. Davies, ``Iterative hard thresholding for compressed
  sensing,'' \emph{Applied and Computational Harmonic Analysis}, vol.~27,
  no.~3, pp. 265 -- 274, 2009.

\bibitem{Foucart:2011:HTP:2340478.2340494}
S.~Foucart, ``Hard thresholding pursuit: An algorithm for compressive
  sensing,'' \emph{SIAM J. Numer. Anal.}, vol.~49, no.~6, pp. 2543--2563, Dec.
  2011.

\bibitem{6145475}
D.~Donoho, Y.~Tsaig, I.~Drori, and J.-L. Starck, ``Sparse solution of
  underdetermined systems of linear equations by stagewise orthogonal matching
  pursuit,'' \emph{Information Theory, IEEE Transactions on}, vol.~58, no.~2,
  pp. 1094--1121, Feb 2012.

\bibitem{YangdeHoog:2014}
M.~Yang and F.~de~Hoog, ``New coherence and rip analysis for weak orthogonal
  matching pursuit,'' in \emph{Statistical Signal Processing (SSP), 2014 IEEE
  Workshop on}, June 2014, pp. 376--379.

\bibitem{Temlyakov:11}
V.~Temlyakov, \emph{Greedy Approximation}.\hskip 1em plus 0.5em minus
  0.4em\relax Cambridge University Press, 2011.

\bibitem{DH}
D.~Donoho and X.~Huo, ``Uncertainty principles and ideal atomic
  decomposition,'' \emph{Information Theory, IEEE Transactions on}, vol.~47,
  no.~7, pp. 2845 --2862, nov 2001.

\bibitem{MR1929464}
M.~Elad and A.~M. Bruckstein, ``A generalized uncertainty principle and sparse
  representation in pairs of bases,'' \emph{IEEE Trans. Inform. Theory},
  vol.~48, no.~9, pp. 2558--2567, 2002.

\bibitem{MR1963681}
D.~L. Donoho and M.~Elad, ``Optimally sparse representation in general
  (nonorthogonal) dictionaries via {$l^1$} minimization,'' \emph{Proceedings of
  the National Academy of Sciences}, vol. 100, no.~5, pp. 2197--2202, 2003.

\bibitem{MR2045813}
R.~Gribonval and M.~Nielsen, ``Sparse representations in unions of bases,''
  \emph{IEEE Trans. Inform. Theory}, vol.~49, no.~12, pp. 3320--3325, 2003.

\bibitem{5361489}
Y.~Eldar and H.~Rauhut, ``Average case analysis of multichannel sparse recovery
  using convex relaxation,'' \emph{Information Theory, IEEE Transactions on},
  vol.~56, no.~1, pp. 505--519, 2010.

\bibitem{5550495}
M.~Davenport and M.~Wakin, ``Analysis of orthogonal matching pursuit using the
  restricted isometry property,'' \emph{Information Theory, IEEE Transactions
  on}, vol.~56, no.~9, pp. 4395--4401, 2010.

\bibitem{HuangZhu:11}
S.~Huang and J.~Zhu, ``Recovery of sparse signals using omp and its variants:
  convergence analysis based on rip,'' \emph{Inverse Problems}, vol.~27, no.~3,
  2011.

\bibitem{6092487}
E.~Liu and V.~Temlyakov, ``The orthogonal super greedy algorithm and
  applications in compressed sensing,'' \emph{Information Theory, IEEE
  Transactions on}, vol.~58, no.~4, pp. 2040--2047, 2012.

\bibitem{6213142}
J.~Wang and B.~Shim, ``On the recovery limit of sparse signals using orthogonal
  matching pursuit,'' \emph{Signal Processing, IEEE Transactions on}, vol.~60,
  no.~9, pp. 4973--4976, Sept 2012.

\bibitem{MoShen:12}
Q.~Mo and Y.~Shen, ``A remark on the restricted isometry property in orthogonal
  matching pursuit,'' \emph{Information Theory, IEEE Transactions on}, vol.~58,
  no.~6, pp. 3654--3656, 2012.

\bibitem{Zhang:2011}
T.~Zhang, ``Sparse recovery with orthogonal matching pursuit under rip,''
  \emph{Information Theory, IEEE Transactions on}, vol.~57, no.~9, pp.
  6215--6221, Sept 2011.

\bibitem{DuarteEldar:2011}
M.~Duarte and Y.~Eldar, ``Structured compressed sensing: From theory to
  applications,'' \emph{Signal Processing, IEEE Transactions on}, vol.~59,
  no.~9, pp. 4053--4085, Sept 2011.

\bibitem{Rauhut:10}
H.~{R}auhut, ``Compressive sensing and structured random matrices,'' in
  \emph{Theoretical Foundations and Numerical Methods for Sparse Recovery},
  ser. Radon Series Comp. Appl. Math., M.~{F}ornasier, Ed.\hskip 1em plus 0.5em
  minus 0.4em\relax deGruyter, 2010, vol.~9, pp. 1--92, corrected Version
  (April 4, 2011): Noncommutative Khintchine inequality for Rademacher chaos
  (Theorem 6.22) corrected, Proof of Theorem 9.3 corrected. Proof of Lemma 8.2
  corrected.

\bibitem{Yang:2011:GAA:2338237}
M.~Yang, ``Greedy algorithms in approximation theory and compressed sensing,''
  Ph.D. dissertation, University of South Carolina, Columbia, SC, USA, 2011,
  aAI3469193.

\bibitem{Temlyakov:08}
V.~Temlyakov, ``\BIBforeignlanguage{English}{Relaxation in greedy
  approximation},'' \emph{\BIBforeignlanguage{English}{Constructive
  Approximation}}, vol.~28, no.~1, pp. 1--25, 2008.

\bibitem{T9}
V.~N. Temlyakov, ``Greedy approximation,'' \emph{Acta Numer.}, vol.~17, pp.
  235--409, 2008.

\end{thebibliography}
