Article
Computer Science, Hardware & Architecture
Haiyang Zou, Wengang Zhao
Summary: In this paper, a scaled null space property method is proposed for sparse signal recovery. By scaling down the vectors in the null space of the sensing matrix, more relaxed RIP conditions are established, ensuring the bounded approximation recovery of sparse signals in bounded noisy environments.
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
(2022)
Article
Engineering, Electrical & Electronic
X. Gao, J. Zhou
Summary: In this paper, a restricted isometry principle based on the L-1 norm (L-1 RIP) is proposed to accurately and stably estimate signal sparsity in the presence of outliers, improving the accuracy of signal recovery. Additionally, an estimation method for the L-1 RIP constant is introduced, allowing for accurate signal reconstruction when the measurement matrix meets the L-1 RIP criterion under the estimated constant.
CIRCUITS SYSTEMS AND SIGNAL PROCESSING
(2022)
Article
Engineering, Electrical & Electronic
Yujia Xie, Xinhua Su, Huanmin Ge
Summary: Recently, non-convex and non-linear metrics have been used in compressed sensing to promote sparsity. This letter proposes an extension of the l(1)/l(2) minimization method for sparse recovery, using the l(1)/l(p) minimization method with p > 1. We establish sufficient conditions for the l(1)/l(p) minimization to recover sparse signals under the restricted isometry property (RIP). Additionally, we develop an effective algorithm to solve the l(1)/l(p) minimization problem. Experimental results show that the proposed method is comparable to state-of-the-art methods for sparse signal recovery.
IEEE SIGNAL PROCESSING LETTERS
(2023)
Article
Computer Science, Information Systems
Lei Shi, Gangrong Qu, Qian Wang
Summary: This article presents a method to improve the restricted isometry constant by weighting the sensing matrix, and verifies its effectiveness through algorithms.
Article
Optics
Xizheng Ke, Jiali Wu, Jiaxuan Hao
Summary: The slope measured by a wavefront sensor has good sparsity in the frequency domain. In this study, the sparsity adaptive matching pursuit algorithm (SAMP) was used to reconstruct the distorted wavefront, which showed shorter reconstruction time and higher accuracy compared to other algorithms. An experiment was conducted to verify the ability of the SAMP algorithm in correcting beam wavefront distortion.
APPLIED PHYSICS B-LASERS AND OPTICS
(2022)
Article
Computer Science, Information Systems
Jun Wang
Summary: In this paper, a wonderful triangle is introduced to explore the concrete metric relationship between llxll1/llxll and llxll0. Based on the analysis of the iterative soft-thresholding operator, the angle of the triangle corresponding to the side llxll. - llxll1/llxll0 is studied, demonstrating the meaningfulness of signal sparsity within a certain exact interval.
INFORMATION SCIENCES
(2022)
Article
Engineering, Electrical & Electronic
Thuong Nguyen Canh, Byeungwoo Jeon
Summary: This work introduces a novel sampling matrix RSRM, aiming to improve sensing and compressing efficiency while maintaining security. RSRM combines the advantages of frame-based and block-based sensing, achieving compressive measurements through random projection of multiple randomly sub-sampled signals, and satisfying the Restricted Isometry Property.
SIGNAL PROCESSING-IMAGE COMMUNICATION
(2021)
Article
Engineering, Electrical & Electronic
Yun-Bin Zhao, Zhi-Quan Luo
Summary: The optimal k-thresholding and optimal k-thresholding pursuit are introduced as frameworks for compressed sensing and signal approximation, leading to the development of efficient algorithms for signal reconstruction. While initial results show stability in signal reconstruction across various sparsity levels, the guaranteed performance for parameters omega >= 2 has yet to be established. This study aims to demonstrate the guaranteed performance of these techniques and establish the first performance results for relaxed optimal k-thresholding and pursuit with omega >= 2, while also providing a numerical comparison with existing methods.
Article
Engineering, Electrical & Electronic
Yuhan Li, Tianyao Huang, Xingyu Xu, Yimin Liu, Lei Wang, Yonina C. Eldar
Summary: This study investigates the phase transitions of range-Doppler recovery in FAR using compressed sensing methods. The results show that block sparse recovery outperforms standard recovery when extended targets occupy multiple range cells, facilitating radar parameter design.
IEEE TRANSACTIONS ON SIGNAL PROCESSING
(2021)
Article
Mathematics, Applied
Chao Wang, Min Tao, Chen-Nee Chuah, James Nagy, Yifei Lou
Summary: This paper explores the L(1)/L(2) minimization on the gradient for imaging applications and demonstrates its superiority over traditional total variation and other nonconvex regularizations through experiments and numerical analysis.
Article
Mathematics, Applied
Jared Tanner, Simon Vary
Summary: Expressing a matrix as the sum of a low-rank matrix plus a sparse matrix is a flexible model for capturing global and local features in data. This model is widely used in robust principle component analysis and dynamic-foreground/static-background separation. Compressed sensing, matrix completion, and their variants have shown that data satisfying low complexity models can be efficiently recovered from a number of measurements proportional to the model complexity. This manuscript presents guarantees that matrices expressed as the sum of a rank-r matrix and a s-sparse matrix can be recovered by computationally tractable methods from a small number of linear measurements. Numerical experiments are provided to support the results. Evaluation: 7/10
APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS
(2023)
Article
Computer Science, Artificial Intelligence
Huanmin Ge, Wengu Chen, Michael K. Ng
Summary: The paper discusses the application and advantages of l(1) - l(2) regularization in signal and image processing, explores more precise conditions for the method, and proposes new analysis techniques and restricted isometry property to guarantee accurate and stable signal recovery.
SIAM JOURNAL ON IMAGING SCIENCES
(2021)
Article
Geochemistry & Geophysics
Bangjie Zhang, Gang Xu, Hanwen Yu, Hui Wang, Hao Pei, Wei Hong
Summary: This article proposes a novel robust gridless compressed sensing (RGLCS) algorithm for high-resolution 3-D imaging. The algorithm uses atomic norm minimization to model the joint-sparsity pattern on elevation distribution between adjacent pixels, and models outliers and disturbances as sparsely distributed spike noise in the image domain. Experimental results validate the effectiveness of the proposed algorithm.
IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING
(2023)
Article
Engineering, Electrical & Electronic
Sanhita Guha, Andreas Bathelt, Miguel Heredia Conde, Joachim Ender
Summary: Existing compressed sensing algorithms fail in radar target detection when there is a large gap in the frequency band. A new algorithm based on a subdivision-fusion scheme is proposed to solve this problem. The algorithm utilizes a structured sensing matrix based on radar signals to achieve good range resolution despite high coherence. The performance of the algorithm is discussed and demonstrated through simulative examples and real measurement data, showing superior performance in the presence of band gaps.
IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING
(2023)
Article
Engineering, Electrical & Electronic
Yingtong Chen, Shoujin Lin
Summary: A preconditioning method is proposed in this study to improve the signal recovery accuracy of CS systems by simultaneously enhancing the RIP of an equivalent dictionary and maintaining the total noise energy, resulting in improved performance of the CS system in a total noise environment.
Article
Mathematics, Applied
Quentin Denoyelle, Vincent Duval, Gabriel Peyre, Emmanuel Soubies
Editorial Material
Mathematics, Applied
Gabriel Peyre, Antonin Chambolle
APPLIED MATHEMATICS AND OPTIMIZATION
(2020)
Article
Biochemical Research Methods
Geert-Jan Huizing, Gabriel Peyre, Laura Cantini
Summary: This paper proposes the use of Optimal Transport (OT) as a cell-cell similarity metric for single-cell omics data, and extensively evaluates it against state-of-the-art metrics on multiple datasets. The results show that OT improves cell-cell similarity inference and cell clustering in various types of single-cell data.
Article
Computer Science, Theory & Methods
Clarice Poon, Nicolas Keriven, Gabriel Peyre
Summary: This article investigates the problem of compressed sensing in continuous domains and analyzes the performance of the BLASSO algorithm. The results show that under certain conditions, the BLASSO algorithm can recover sparse vectors in a stable manner in continuous domains.
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS
(2023)
Article
Statistics & Probability
Clarice Poon, Gabriel Peyre
Summary: The degrees of freedom quantify the number of parameters of an estimator and play a central role in risk minimization procedures. This study focuses on continuous methods and introduces a new formula for the unbiased estimation of the degrees of freedom, which differs from the formula used in finite dimensional linear models. The study also explores the application of this formula in the context of super-resolution and multilayer perceptron, providing numerical results to support the findings.
Article
Computer Science, Software Engineering
Clarice Poon, Gabriel Peyre
Summary: Non-smooth optimization is a crucial component in many imaging or machine learning pipelines, encoding structural constraints and enabling the use of robust loss functions. Traditional approaches require parameter tuning or support pruning, but this work proposes a different approach involving a smooth over-parameterization. The main theoretical and algorithmic contributions connect gradient descent to a varying Hessian metric and apply the Variable Projection method for improved convergence.
MATHEMATICAL PROGRAMMING
(2023)
Proceedings Paper
Computer Science, Artificial Intelligence
Meyer Scetbon, Gabriel Peyre, Marco Cuturi
Summary: The ability to align points across different spaces is crucial in machine learning, and the Gromov-Wasserstein framework provides a solution by seeking a low-distortion, geometry-preserving assignment between these points. However, the traditional approach to solving this problem has a cubic complexity. This paper presents a recent variant of the optimal transport problem that restricts the set of admissible couplings, enabling a more efficient computation of the Gromov-Wasserstein problem in linear time.
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 162
(2022)
Proceedings Paper
Computer Science, Artificial Intelligence
Geert-Jan Huizing, Laura Cantini, Gabriel Peyre
Summary: Defining meaningful distances between samples in a dataset is a fundamental problem in machine learning. Optimal Transport (OT) transforms distances between features into geometrically meaningful distances between samples. However, choosing the ground metric is not straightforward, especially in the absence of labels. This paper proposes a method to simultaneously compute OT distances between samples and features, ensuring the existence and uniqueness of these distance matrices.
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 162
(2022)
Proceedings Paper
Computer Science, Artificial Intelligence
Pierre Ablin, Gabriel Peyre
Summary: The landing algorithm is a method to minimize a function over the manifold of orthogonal matrices. It evolves the matrix along a direction guided by potential energy, without using expensive retractions. It is faster and less prone to numerical errors compared to retraction-based methods.
INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 151
(2022)
Proceedings Paper
Computer Science, Artificial Intelligence
Michael E. Sander, Pierre Ablin, Mathieu Blondel, Gabriel Peyre
Summary: In this paper, we propose a attention-based model called Sinkformer, which uses Sinkhorn's algorithm to make attention matrices doubly stochastic. We show that this normalization allows us to interpret the iterations of self-attention modules as a discretized gradient-flow for the Wasserstein metric. Moreover, we demonstrate that Sinkformers operate a heat diffusion in the infinite number of samples limit. We also provide experimental evidence that Sinkformers enhance model accuracy in vision and natural language processing tasks.
INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 151
(2022)
Proceedings Paper
Computer Science, Artificial Intelligence
Othmane Sebbouh, Marco Cuturi, Gabriel Peyre
Summary: An increasing number of machine learning problems require minimizing a loss function that is itself defined as a maximum. We propose RSGDA, a variant algorithm with simpler theoretical analysis and almost sure convergence rates.
INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 151
(2022)
Proceedings Paper
Computer Science, Artificial Intelligence
Thibault Sejourne, Francois-Xavier Vialard, Gabriel Peyre
Summary: Unbalanced optimal transport (UOT) extends optimal transport (OT) to consider mass variations when comparing distributions. This work introduces two new algorithms to improve the convergence speed of UOT, and numerical simulations validate their effectiveness.
INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 151
(2022)
Proceedings Paper
Computer Science, Artificial Intelligence
Michael E. Sander, Pierre Ablin, Mathieu Blondel, Gabriel Peyre
Summary: The paper introduces Momentum ResNets as an alternative to ResNets, showing that they have similar accuracy but a smaller memory footprint, making them promising for fine-tuning models.
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 139
(2021)
Proceedings Paper
Computer Science, Artificial Intelligence
Meyer Scetbon, Marco Cuturi, Gabriel Peyre
Summary: Recent studies have shown that approximating kernel matrices with low-rank factors and imposing low-nonnegative rank constraints in OT problems are promising approaches in machine learning. A generic algorithm has been proposed to address OT problems under low-nonnegative rank constraints with arbitrary costs, and its efficiency has been demonstrated in benchmark experiments.
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 139
(2021)
Article
Computer Science, Artificial Intelligence
Matthieu Heitz, Nicolas Bonneel, David Coeurjolly, Marco Cuturi, Gabriel Peyre
Summary: Optimal transport distances between probability distributions are heavily influenced by the choice of ground metric parameter. By learning geodesic distance on a graph that supports the measures of interest, the ground metric learning problem can be more efficiently addressed. This approach can be applied to solving inverse problems stemming from density observations and modeling mass displacements in natural phenomena.
JOURNAL OF MATHEMATICAL IMAGING AND VISION
(2021)
Article
Mathematics, Applied
Muhammad Syifa'ul Mufid, Ebrahim Patel, Sergei Sergeev
Summary: This paper presents an approach to solve maxmin-omega linear systems by performing normalization and generating a principal order matrix. The possible solution indices can be identified using the principal order matrix and the parameter omega, and the fully active solutions can be obtained from these indices. Other solutions can be found by applying a relaxation to the fully active solutions. This approach can be seen as a generalization of solving max-plus or min-plus linear systems. The paper also highlights the unusual feature of maxmin-omega linear systems having a finite number of solutions when the solution is non-unique.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
E. Mainar, J. M. Pena, B. Rubio
Summary: A bidiagonal decomposition of quantum Hilbert matrices is obtained and the total positivity of these matrices is proved. This factorization is used for accurate algebraic computations and the numerical errors caused by imprecise computer arithmetic or perturbed input data are analyzed. Numerical experiments demonstrate the accuracy of the proposed methods.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Zhong-Zhi Bai
Summary: This study explores the algebraic structures and computational properties of Wasserstein-1 metric matrices. It shows that these matrices can be expressed using the Neumann series of nilpotent matrices and can be accurately and stably computed by solving unit bidiagonal triangular systems of linear equations.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Bogdan Nica
Summary: This study investigates the relationship between the independence number and chromatic number in a graph of non-singular matrices over a finite field, and obtains an upper bound for the former and a lower bound for the latter.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Dijian Wang, Yaoping Hou, Deqiong Li
Summary: In this paper, a Turán-like problem in signed graphs is studied. The properties of signed graphs are proven in the context of the problem.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Tyler Chen, Thomas Trogdon
Summary: This study focuses on the stability of the Lanczos algorithm when applied to problems with eigenvector empirical spectral distribution close to a reference measure characterized by well-behaved orthogonal polynomials. The analysis reveals that the Lanczos algorithm is forward stable on many large random matrix models, even in finite precision arithmetic, which indicates that random matrices differ significantly from general matrices and caution must be exercised when using them to test numerical algorithms.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Constantin Costara
Summary: This passage discusses linear mappings on matrices and the relationship between subsets of the spectrum, providing corresponding characterization conditions.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Amir Hossein Ghodrati, Mohammad Ali Hosseinzadeh
Summary: This paper presents tight upper bounds for all signless Laplacian eigenvalues of a graph with prescribed order and minimum degree, improving upon previously known bounds. Additionally, the relationship between the number of signless Laplacian eigenvalues falling within specific intervals and various graph parameters such as independence, clique, chromatic, edge covering, and matching numbers is explored.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Ya-Lei Jin, Jie Zhang, Xiao-Dong Zhang
Summary: This paper investigates the relationship between the spectral radius of a symmetric matrix and its principal submatrices, and uses these relationships to obtain upper bounds of the spectral radius of graphs.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Davide Bolognini, Paolo Sentinelli
Summary: We introduce immanant varieties associated with simple characters of a finite group and discuss the features of one-dimensional characters and trivial characters.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
A. S. Gordienko
Summary: We introduce the concept of a graded group action on a graded algebra, or equivalently, a group action by graded pseudoautomorphisms. We study the properties of groups of graded pseudoautomorphisms and prove several important theorems and conjectures regarding graded algebras with a group action.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Jiaqi Gu, Shenghao Feng, Yimin Wei
Summary: We propose a tensor product structure compatible with the hypergraph structure and define the algebraic connectivity of the hypergraph in this product, establishing its relationship with vertex connectivity. We introduce connectivity optimization problems into the hypergraph and solve them using algebraic connectivity. Additionally, we apply the Laplacian eigenmap algorithm to the hypergraph under our tensor product.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
Article
Mathematics, Applied
Samuel Lichtenberg, Abiy Tasissa
Summary: This paper explores a dual basis approach to Classical Multidimensional Scaling (CMDS) and provides explicit formulas for the dual basis vectors. It also characterizes the spectrum of an essential matrix in the dual basis framework. Connections to a related problem in metric nearness are made.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2024)
