Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares

In countless applications, we need to reconstruct a $K$-sparse signal $\mathbf{x}\in\mathbb{R}^n$ from noisy measurements $\mathbf{y}=\mathbf{\Phi}\mathbf{x}+\mathbf{v}$, where $\mathbf{\Phi}\in\mathbb{R}^{m\times n}$ is a sensing matrix and $\mathbf{v}\in\mathbb{R}^m$ is a noise vector. Orthogonal least squares (OLS), which selects at each step the column that results in the most significant decrease in the residual power, is one of the most popular sparse recovery algorithms. In this paper, we investigate the number of iterations required for recovering $\mathbf{x}$ with the OLS algorithm. We show that OLS provides a stable reconstruction of all $K$-sparse signals $\mathbf{x}$ in $\lceil2.8K\rceil$ iterations provided that $\mathbf{\Phi}$ satisfies the restricted isometry property (RIP). Our result provides a better recovery bound and fewer number of required iterations than those proposed by Foucart in 2013.     

基于基底合并的分片稀疏恢复

如我们所知,诸如视频和图像等信号可以在某些框架下被表示为稀疏信号,因此稀疏恢复(或稀疏表示)是信号处理、图像处理、计算机视觉、机器学习等领域中被广泛研究的问题之一.通常大多数在稀疏恢复中的有效快速算法都是基于求解$l^0$或者$l^1$优化问题.但是,对于求解$l^0$或者$l^1$优化问题以及相关算法所得到的理论充分性条件对信号的稀疏性要求过严.考虑到在很多实际应用中,信号是具有一定结构的,也即,信号的非零元素具有一定的分布特点.在本文中,我们研究分片稀疏恢复的唯一性条件和可行性条件.分片稀疏性是指一个稀疏信号由多个稀疏的子信号合并所得.相应的采样矩阵是由多个基底合并组成.考虑到采样矩阵的分块结构,我们引入了子矩阵的互相干性,由此可以得到相应$l^0$或者$l^1$优化问题可精确恢复解的稀疏度的新上界.本文结果表明.通过引入采样矩阵的分块结构信息.可以改进分片稀疏恢复的充分性条件.以及相应$l^0$或者$l^1$优化问题整体稀疏解的可靠性条件.     

Weighted $\ell_p$-Minimization for Sparse Signal Recovery under Arbitrary Support Prior

Weighted $\ell_p$ ($0相似文献   

Compactness of the solution operator to differential operators in several complex dimensions

We show that the canonical solution operator to the partial differential operators $\tfrac{{\partial ^k }}{{\partial ^k \bar z_i }}(1 \leqslant i \leqslant k)$ restricted to the Bergman-space of the unit poly-disc is not compact, while the canonical solution operator to the partial differential operators $\tfrac{{\partial ^k }}{{\partial \bar z_1 \cdots \partial \bar z_k }}$ restricted to the Bergman-space of the unit poly-disc is compact. This highlights a further (operator-theoretic) difference in the theory of one and several complex variables.     

Metrically Regular Mapping and Its Utilization to Convergence Analysis of a Restricted Inexact Newton-Type Method

In the present paper,we study the restricted inexact Newton-type method for solving the generalized equation 0∈f(x)+F(x),where X and Y are Banach spaces,f:X→Y is a Frechet differentiable function and F:X■Y is a set-valued mapping with closed graph.We establish the convergence criteria of the restricted inexact Newton-type method,which guarantees the existence of any sequence generated by this method and show this generated sequence is convergent linearly and quadratically according to the particular assumptions on the Frechet derivative of f.Indeed,we obtain semilocal and local convergence results of restricted inexact Newton-type method for solving the above generalized equation when the Frechet derivative of f is continuous and Lipschitz continuous as well as f+F is metrically regular.An application of this method to variational inequality is given.In addition,a numerical experiment is given which illustrates the theoretical result.     

On equalities of BLUEs for a multiple restricted partitioned linear model

For the multiple restricted partitioned linear model ${\mathscr{M}}=\{y, X_1$ $\beta_1+\cdots+X_s\beta_s\mid A_1\beta_1=b_1, \cdots, A_s\beta_s=b_s, \Sigma\}$, the relationships between the restricted partitioned linear model ${\mathscr{M}}$ and the corresponding $s$ small restricted linear models ${\mathscr{M}}_i=\{y, X_i\beta_i\mid A_i\beta_i=b_i, \Sigma\},~i=1, \cdots , s$ are studied. The necessary and sufficient conditions for the best linear unbiased estimators $(\mbox{BLUEs})$ under the full restricted model to be the sums of BLUEs under the $s$ small restricted model are derived. Some statistical properties of the \mbox{BLUEs} are also described.     

RECOVERY BASED FINITE ELEMENT METHOD FOR BIHARMONIC EQUATION IN 2D

We design and numerically validate a recovery based linear finite element method for solving the biharmonic equation.The main idea is to replace the gradient operator▽on linear finite element space by G(▽)in the weak formulation of the biharmonic equation,where G is the recovery operator which recovers the piecewise constant function into the linear finite element space.By operator G,Laplace operator△is replaced by▽·G(▽).Furthermore,the boundary condition on normal derivative▽u-n is treated by the boundary penalty method.The explicit matrix expression of the proposed method is also introduced.Numerical examples on the uniform and adaptive meshes are presented to illustrate the correctness and effectiveness of the proposed method.     

Microlocal Analysis of the Doppler Transform on R<Superscript>3</Superscript>

The Doppler transform of a vector field $F = (f_1,f_2,f_3)$ on $\mathbb{R}^3$ is defined by \[\displaystyle\mathcal{D}F(x,\omega) = \sum_j\int_\mathbb{R} \omega_j f_j(x+t\omega)\, dt~,\] where $x\in \mathbb{R}^3$ and $\omega \in S^2$ specifies the direction of a line passing through $x$. In practical applications, $\mathcal{D}F$ is known only for a small subset of lines in $\mathbb{R}^3$. In this article, we deal with the case of $\mathcal{D}F$ restricted to all lines passing through a fixed smooth curve. Using techniques from microlocal analysis, we study the problem of recovering the wavefront set of $\mbox{curl}(F)$ from that of the restricted Doppler transform of $F$.     

图限制下合作对策的τ值

首先研究了图限制下合作对策的τ值,这个单值解是由Tijs提出的经典合作对策τ值的推广.并且当合作图为完全图时,准均衡图对策的τ值与经典合作对策下的准均衡对策的τ值一致.其次利用分支有效性,S-均衡下的相对不变性和限制成比例性讨论了τ值的公理化方法.最后介绍了两类特殊图对策的τ值.     

Blockwise Perturbation Theory for 2x2 Block Markov Chains

Let P be a transition matrix of a Markov chain and be of the form $$P=\Bigg( \begin{matrix} P_{11} &P_{12} \\P_{21} &P_{22} \end{matrix} \Bigg).$$ The stationary distribution $π^T$ is partitioned conformally in the form $(π^T_1, π^T_2)$. This paper establish the relative error bound in $π^T_i (i=1,2)$ when each block $P_{ij}$ get a small relative perturbation.     

一类限制m元over-分拆同余式

We discuss a family of restricted m-ary overpartition functions bm,j （n）, which is the number of m-ary overpartitions of n with at most i ＋ j copies of the non-overlined part m^i allowed, and obtain a family of congruences for bm,lm-1 （n）.     

Littlewood-Paley Formulas and Carleson Measures for Weighted Fock Spaces Induced by A ∞ $A_{\infty }$ -Type Weights

Potential Analysis - We obtain Littlewood-Paley formulas for Fock spaces ${\mathcal {F}}_{\beta ,\omega }^{q}$ induced by weights $\omega \in {A}_{\infty }^{restricted} = \cup _{1 \le p &lt;...     

限制Hamiltonian型及Contact型李代数的不可约表示

设L=H（2r;1）或K（2r+1;1）是定义在特征p>2的代数封闭域F上的限制Hamiltonian型或Contact型李代数.在对广义Jacobson-Witt代数及特殊代数不可约表示的研究基础上,通过定义L的如下阶化:L=L_[q],I,其中I是{1,2,…,r}的子集,得到当p-特征函数χ是正则半单时,所有不可约U_χ（L）-模都是从不可约U_χ(L_[O].I)-模诱导的.     

Character Formulas for a Class of Simple Restricted Modules over the Simple Lie Superalgebras of Witt Type

Let F be an algebraically closed field of prime characteristic, and W(m, n, 1) be the simple restricted Lie superalgebra of Witt type over F, which is the Lie superalgebra of superderivations of the superalgebra ■(m; 1) ■∧(n), where ■(m; 1) is the truncated polynomial algebra with m indeterminants and ∧(n) is the Grassmann algebra with n indeterminants. In this paper, the author determines the character formulas for a class of simple restricted modules of W(m, n, 1) with atypical weights of type Ⅰ.     

Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers

We study the approximation problem (or problem of optimal recovery in the $L_2$-norm) for weighted Korobov spaces with smoothness parameter $\a$. The weights $\gamma_j$ of the Korobov spaces moderate the behavior of periodic functions with respect to successive variables. The nonnegative smoothness parameter $\a$ measures the decay of Fourier coefficients. For $\a=0$, the Korobov space is the $L_2$ space, whereas for positive $\a$, the Korobov space is a space of periodic functions with some smoothness and the approximation problem corresponds to a compact operator. The periodic functions are defined on $[0,1]^d$ and our main interest is when the dimension $d$ varies and may be large. We consider algorithms using two different classes of information. The first class $\lall$ consists of arbitrary linear functionals. The second class $\lstd$ consists of only function values and this class is more realistic in practical computations. We want to know when the approximation problem is tractable. Tractability means that there exists an algorithm whose error is at most $\e$ and whose information cost is bounded by a polynomial in the dimension $d$ and in $\e^{-1}$. Strong tractability means that the bound does not depend on $d$ and is polynomial in $\e^{-1}$. In this paper we consider the worst case, randomized, and quantum settings. In each setting, the concepts of error and cost are defined differently and, therefore, tractability and strong tractability depend on the setting and on the class of information. In the worst case setting, we apply known results to prove that strong tractability and tractability in the class $\lall$ are equivalent. This holds if and only if $\a>0$ and the sum-exponent $s_{\g}$ of weights is finite, where $s_{\g}= \inf\{s>0 : \xxsum_{j=1}^\infty\g_j^s\,<\,\infty\}$. In the worst case setting for the class $\lstd$ we must assume that $\a>1$ to guarantee that functionals from $\lstd$ are continuous. The notions of strong tractability and tractability are not equivalent. In particular, strong tractability holds if and only if $\a>1$ and $\xxsum_{j=1}^\infty\g_j<\infty$. In the randomized setting, it is known that randomization does not help over the worst case setting in the class $\lall$. For the class $\lstd$, we prove that strong tractability and tractability are equivalent and this holds under the same assumption as for the class $\lall$ in the worst case setting, that is, if and only if $\a>0$ and $s_{\g} < \infty$. In the quantum setting, we consider only upper bounds for the class $\lstd$ with $\a>1$. We prove that $s_{\g}<\infty$ implies strong tractability. Hence for $s_{\g}>1$, the randomized and quantum settings both break worst case intractability of approximation for the class $\lstd$. We indicate cost bounds on algorithms with error at most $\e$. Let $\cc(d)$ denote the cost of computing $L(f)$ for $L\in \lall$ or $L\in \lstd$, and let the cost of one arithmetic operation be taken as unity. The information cost bound in the worst case setting for the class $\lall$ is of order $\cc (d) \cdot \e^{-p}$ with $p$ being roughly equal to $2\max(s_\g,\a^{-1})$. Then for the class $\lstd$ in the randomized setting, we present an algorithm with error at most $\e$ and whose total cost is of order $\cc(d)\e^{-p-2} + d\e^{-2p-2}$, which for small $\e$ is roughly $$ d\e^{-2p-2}. $$ In the quantum setting, we present a quantum algorithm with error at most $\e$ that uses about only $d + \log \e^{-1}$ qubits and whose total cost is of order $$ (\cc(d) +d) \e^{-1-3p/2}. $$ The ratio of the costs of the algorithms in the quantum setting and the randomized setting is of order $$ \frac{d}{\cc(d)+d}\,\left(\frac1{\e}\right)^{1+p/2}. $$ Hence, we have a polynomial speedup of order $\e^{-(1+p/2)}$. We stress that $p$ can be arbitrarily large, and in this case the speedup is huge.     

ENHANCED BLOCK-SPARSE SIGNAL RECOVERY PERFORMANCE VIA TRUNCATED e2/e1-2 MINIMIZATION

In this paper, we investigate truncated $ℓ_2/ℓ_{1−2}$ minimization and its associated alternating direction method of multipliers (ADMM) algorithm for recovering the block sparse signals. Based on the block restricted isometry property (Block-RIP), a theoretical analysis is presented to guarantee the validity of proposed method. Our theoretical results not only show a less error upper bound, but also promote the former recovery condition of truncated ℓ₁₋₂ method for sparse signal recovery. Besides, the algorithm has been compared with some state-of-the-art algorithms and numerical experiments have shown excellent performances on recovering the block sparse signals.     

Optimal-Order Parameter Identification in Solving Nonlinear Systems in a Banach Space

We study the sufficient and necessary conditions of the convergence for parameter-based rational methods in a Banach space. We derive a closed form of error bounds in terms of a real parameter $\lambda$ ($1 \leq \lambda < 2$). We also discuss some behaviors when the family is applied to abstract quadratic functions on a Banach space for $ \lambda = 2 $.     

Nodal Solutions of the Brezis-Nirenberg Problem in Dimension 6

We show that the classical Brezis-Nirenberg problem $$-\Delta u=u|u|+\lambda u \ \ \ \ \ \ \ in \ \ \ \Omega, \\ u=0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ on \ \ \ \partial\Omega,$$ when $\Omega$ is a bounded domain in $\mathbb R^6$ has a sign-changing solution which blows-up at a point in $\Omega$ as $\lambda$ approaches a suitable value $\lambda_0>0.$     

THE MINIMAX DIRECTION FOR THE DIRECT PRODUCT OF A CONVEX CONE WITH ITS APPLICATION TO TESTING PROBLEMS

Let C be a closed convex cone in R~k and let C~p be the p-th direct product of C.Thispaper gives some results of the minimax direction with respect to C~p and an innerproduct based on(?),where is a k×k diagonal matrix with positive diagonalelements,is a p×p positive definite matrix and is the Kronecker product ofand.It is also shown that the results may be applied to test the homogeneity of knormal mean vectors where the mean vectors are restricted by a given partial order.     

�лָ������ɷ�֧���̵�Feller����

首先, 当$Q$是一个拟单调的q矩阵的时候, 我们找出最小的$Q$函数是一个Feller的转移函数的准则. 然后我们把这个结论应用于生成分支q矩阵并得到相应的生成分支过程的Feller准则. 特别地, 设$\theta$是分支q矩阵中的非线性数, 总是存在一个分点$\theta_0$满足$1\leq\theta_0\leq2$或$\theta_0<+\infty$使得 生成分支过程是否是Feller的要依据$\theta<\theta_0$或者$\theta>\theta_0$.