Infinite-Dimensional Compressed Sensing and Function Interpolation

We introduce and analyse a framework for function interpolation using compressed sensing. This framework—which is based on weighted \(\ell ^1\) minimization—does not require a priori bounds on the expansion tail in either its implementation or its theoretical guarantees and in the absence of noise leads to genuinely interpolatory approximations. We also establish a new recovery guarantee for compressed sensing with weighted \(\ell ^1\) minimization based on this framework. This guarantee conveys several benefits. First, unlike existing results, it is sharp (up to constants and log factors) for large classes of functions regardless of the choice of weights. Second, by examining the measurement condition in the recovery guarantee, we are able to suggest a good overall strategy for selecting the weights. In particular, when applied to the important case of multivariate approximation with orthogonal polynomials, this weighting strategy leads to provably optimal estimates on the number of measurements required, whenever the support set of the significant coefficients is a so-called lower set. Finally, this guarantee can also be used to theoretically confirm the benefits of alternative weighting strategies where the weights are chosen based on prior support information. This provides a theoretical basis for a number of recent numerical studies showing the effectiveness of such approaches.     

Generalized Sampling and Infinite-Dimensional Compressed Sensing

We introduce and analyze a framework and corresponding method for compressed sensing in infinite dimensions. This extends the existing theory from finite-dimensional vector spaces to the case of separable Hilbert spaces. We explain why such a new theory is necessary by demonstrating that existing finite-dimensional techniques are ill suited for solving a number of key problems. This work stems from recent developments in generalized sampling theorems for classical (Nyquist rate) sampling that allows for reconstructions in arbitrary bases. A conclusion of this paper is that one can extend these ideas to allow for significant subsampling of sparse or compressible signals. Central to this work is the introduction of two novel concepts in sampling theory, the stable sampling rate and the balancing property, which specify how to appropriately discretize an infinite-dimensional problem.     

Fast Binary Embeddings and Quantized Compressed Sensing with Structured Matrices

This paper deals with two related problems, namely distance-preserving binary embeddings and quantization for compressed sensing. First, we propose fast methods to replace points from a subset Χ ⊂ ℝⁿ , associated with the euclidean metric, with points in the cube {±1}^m , and we associate the cube with a pseudometric that approximates euclidean distance among points in Χ. Our methods rely on quantizing fast Johnson-Lindenstrauss embeddings based on bounded orthonormal systems and partial circulant ensembles, both of which admit fast transforms. Our quantization methods utilize noise shaping, and include sigma-delta schemes and distributed noise-shaping schemes. The resulting approximation errors decay polynomially and exponentially fast in m, depending on the embedding method. This dramatically outperforms the current decay rates associated with binary embeddings and Hamming distances. Additionally, it is the first such binary embedding result that applies to fast Johnson-Lindenstrauss maps while preserving ℓ₂ norms. Second, we again consider noise-shaping schemes, albeit this time to quantize compressed sensing measurements arising from bounded orthonormal ensembles and partial circulant matrices. We show that these methods yield a reconstruction error that again decays with the number of measurements (and bits), when using convex optimization for reconstruction. Specifically, for sigma-delta schemes, the error decays polynomially in the number of measurements, and it decays exponentially for distributed noise-shaping schemes based on beta encoding. These results are near optimal and the first of their kind dealing with bounded orthonormal systems. © 2019 Wiley Periodicals, Inc.     

The Geometry of Off-the-Grid Compressed Sensing

Foundations of Computational Mathematics - Compressed sensing (CS) ensures the recovery of sparse vectors from a number of randomized measurements proportional to their sparsity. The initial theory...     

Some Properties for the Euclidean Distance Matrix and Positive Semidefinite Matrix Completion Problems

The Euclidean distance matrix (EDM) completion problem and the positive semidefinite (PSD) matrix completion problem are considered in this paper. Approaches to determine the location of a point in a linear manifold are studied, which are based on a referential coordinate set and a distance vector whose components indicate the distances from the point to other points in the set. For a given referential coordinate set and a corresponding distance vector, sufficient and necessary conditions are presented for the existence of such a point that the distance vector can be realized. The location of the point (if it exists) given by the approaches in a linear manifold is independent of the coordinate system, and is only related to the referential coordinate set and the corresponding distance vector. An interesting phenomenon about the complexity of the EDM completion problem is described. Some properties about the uniqueness and the rigidity of the conformation for solutions to the EDM and PSD completion problems are presented.     

基于随机矩阵的差分代换算法的完备化

本文利用有限核原理,给出了基于随机矩阵的逐次差分代换方法的一个完备化.获得了判定多项式半正定性的完全算法.此算法可进一步应用于计算有理函数的全局最优值.与常用的数值最优化方法不同的是,本方法获得的是精确符号解.     

Analysis of Singular Value Thresholding Algorithm for Matrix Completion

Journal of Fourier Analysis and Applications - This paper provides analysis for convergence of the singular value thresholding algorithm for solving matrix completion and affine rank minimization...     

Stability and Instance Optimality for Gaussian Measurements in Compressed Sensing

In compressed sensing, we seek to gain information about a vector x∈ℝ ^N from d ≪ N nonadaptive linear measurements. Candes, Donoho, Tao et al. (see, e.g., Candes, Proc. Intl. Congress Math., Madrid, 2006; Candes et al., Commun. Pure Appl. Math. 59:1207–1223, 2006; Donoho, IEEE Trans. Inf. Theory 52:1289–1306, 2006) proposed to seek a good approximation to x via ℓ ₁ minimization. In this paper, we show that in the case of Gaussian measurements, ℓ ₁ minimization recovers the signal well from inaccurate measurements, thus improving the result from Candes et al. (Commun. Pure Appl. Math. 59:1207–1223, 2006). We also show that this numerically friendly algorithm (see Candes et al., Commun. Pure Appl. Math. 59:1207–1223, 2006) with overwhelming probability recovers the signal with accuracy, comparable to the accuracy of the best k-term approximation in the Euclidean norm when k∼d/ln N.     

压缩感知在化学交换饱和传递磁共振成像中的应用

化学交换饱和转移(CEST)磁共振成像(MRI)技术越来越多地应用于探测细胞蛋白质及其微环境属性的研究,在临床方面显示巨大的应用前景.但由于蛋白质浓度较低和采集的信号灵敏度较差,获取CEST MRI需要花费较长的时间.我们试图在满足CESTR MRI定量分析精度要求的条件下,通过压缩感知技术减少图像采集时间.实验测量数据结果显示压缩感知在数据降采样率小于等于5的条件下获取CEST的定量效应与完整采样获取的数据无显著性的差异.研究表明压缩感知应用于CEST MRI是可行的.     

离散时间投资组合保险策略CPPI及其实证分析

本文重点讨论了在离散时刻对投资组合进行调整的CPPI策略.给出了组合价值的过程表达式,并对其进行风险分析;引入二次期望效用函数,给出了确定CPPI策略中最优乘数的方法;讨论了借贷限制对CPPI策略的影响并将其与买入持有策略进行比较分析。最后,文章对CPPI策略的投资效果进行了实证分析.     

用无限阶Toeplitz矩阵求常系数微分方程的级数解

无限阶Toeplitz矩阵的属于0的特征向量可递推地求得,可表示常系数齐次微分方程的解.用它的逆可求得常系数非齐次微分方程的特解.     

Gram Matrix Analysis of Finite Distance Spaces in Constant Curvature

We develop the utility of Gram matrix machinery as a tool to treat the geometry of simplices in space forms. A formula relating the determinant of a normalized Gram matrix to the geometry of the simplex it represents is presented. We then apply the tools to leaf spaces, i.e. the set of degree 1 vertices of a metric tree. One main result is that for a given metric space X there exists a constant ₀ < 0, such that X embeds into all hyperbolic spaces of curvature less than ₀, if and only if X is a leaf space.     

Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion: Some Statistical and Algorithmic Theory for Adaptive-Impute

Over the past decade, various matrix completion algorithms have been developed. Thresholded singular value decomposition (SVD) is a popular technique in implementing many of them. A sizable number of studies have shown its theoretical and empirical excellence, but choosing the right threshold level still remains as a key empirical difficulty. This article proposes a novel matrix completion algorithm which iterates thresholded SVD with theoretically justified and data-dependent values of thresholding parameters. The estimate of the proposed algorithm enjoys the minimax error rate and shows outstanding empirical performances. The thresholding scheme that we use can be viewed as a solution to a nonconvex optimization problem, understanding of whose theoretical convergence guarantee is known to be limited. We investigate this problem by introducing a simpler algorithm, generalized- softImpute, analyzing its convergence behavior, and connecting it to the proposed algorithm.     

常系数线性微分方程组的基解矩阵的一种新求法

在求解常系数线性微分方程组时,关键是基解矩阵的计算.给出了利用哈密顿—凯莱定理计算基解矩阵的一种方法,并通过实例说明了这种方法的特点和在简化计算方面的有效性.     

基于BIB设计关联矩阵的最优二元等重码

以平衡不完全区组设计的二元关联矩阵为基础研究了二元等距等重码(n,M,2δ,ω),并且研究了这个二元等重码成为最优等重码的条件,找出了一个最优检错码.     

Compressed sensing with structured sparsity and structured acquisition

Compressed Sensing (CS) is an appealing framework for applications such as Magnetic Resonance Imaging (MRI). However, up-to-date, the sensing schemes suggested by CS theories are made of random isolated measurements, which are usually incompatible with the physics of acquisition. To reflect the physical constraints of the imaging device, we introduce the notion of blocks of measurements: the sensing scheme is not a set of isolated measurements anymore, but a set of groups of measurements which may represent any arbitrary shape (parallel or radial lines for instance). Structured acquisition with blocks of measurements are easy to implement, and provide good reconstruction results in practice. However, very few results exist on the theoretical guarantees of CS reconstructions in this setting. In this paper, we derive new CS results for structured acquisitions and signals satisfying a prior structured sparsity. The obtained results provide a recovery probability of sparse vectors that explicitly depends on their support. Our results are thus support-dependent and offer the possibility for flexible assumptions on the sparsity structure. Moreover, the results are drawing-dependent, since we highlight an explicit dependency between the probability of reconstructing a sparse vector and the way of choosing the blocks of measurements. Numerical simulations show that the proposed theory is faithful to experimental observations.     

COMPLETE HYPERSURFACES WITH CONSTANT SCALAR CURVATURE AND CONSTANT MEAN CURVATURE IN R~4

Let M be a 3-dimersional complete and connected hypersurface immersed in R~4. If thescalar curvature R and the mean curvature |H| of M are constants, where |H|≠0, R≥0,then there are only three cases: R=6|H|~2, 9/2|H|~2 and 0. Moreovon we can find somehypersurfaces appropriate to these cases.