Search

The matrix recovery (completion) problem, a central problem in data science and theoretical computer science, is to recover a matrix $A$ from a relatively small sample of entries. While such a task is impossible in general, it has been shown that one can recover $A$ exactly in polynomial time, with high probability, from a random subset of entries, under three (basic and necessary) assumptions: (1) the rank of $A$ is very small compared to its dimensions (low rank), (2) $A$ has delocalized singular vectors (incoherence), and (3) the sample size is sufficiently large. There are many different algorithms for the task, including convex optimization by Candes, Tao and Recht (2009), alternating projection by Hardt and Wooters (2014) and low rank approximation with gradient descent by Keshavan, Montanari and Oh (2009, 2010). In applications, it is more realistic to assume that data is noisy. In this case, these approaches provide an approximate recovery with small root mean square error. However, it is hard to transform such approximate recovery to an exact one. Recently, results by Abbe et al. (2017) and Bhardwaj et al. (2023) concerning approximation in the infinity norm showed that we can achieve exact recovery even in the noisy case, given that the ground matrix has bounded precision. Beyond the three basic assumptions above, they required either the condition number of $A$ is small (Abbe et al.) or the gap between consecutive singular values is large (Bhardwaj et al.). In this paper, we remove these extra spectral assumptions. As a result, we obtain a simple algorithm for exact recovery in the noisy case, under only three basic assumptions. This is the first such algorithm. To analyse the algorithm, we introduce a contour integration argument which is totally different from all previous methods and may be of independent interest., Comment: 56 pages, 1 figure

We introduce a novel framework for decomposing interventional causal effects into synergistic, redundant, and unique components, building on the intuition of Partial Information Decomposition (PID) and the principle of M\"obius inversion. While recent work has explored a similar decomposition of an observational measure, we argue that a proper causal decomposition must be interventional in nature. We develop a mathematical approach that systematically quantifies how causal power is distributed among variables in a system, using a recently derived closed-form expression for the M\"obius function of the redundancy lattice. The formalism is then illustrated by decomposing the causal power in logic gates, cellular automata, and chemical reaction networks. Our results reveal how the distribution of causal power can be context- and parameter-dependent. This decomposition provides new insights into complex systems by revealing how causal influences are shared and combined among multiple variables, with potential applications ranging from attribution of responsibility in legal or AI systems, to the analysis of biological networks or climate models., Comment: 10 pages, 6 figures

In today's financial markets, quantitative trading has become an essential trading method, with the MACD indicator widely employed in quantitative trading strategies. This paper begins by screening and cleaning the dataset, establishing a model that adheres to the basic buy and sell rules of the MACD, and calculating key metrics such as the win rate, return, Sharpe ratio, and maximum drawdown for each stock. However, the MACD often generates erroneous signals in highly volatile markets. To address this, wavelet transform is applied to reduce noise, smoothing the DIF image, and a model is developed based on this to optimize the identification of buy and sell points. The results show that the annualized return has increased by 5%, verifying the feasibility of the method. Subsequently, the divergence principle is used to further optimize the trading strategy, enhancing the model's performance. Additionally, a genetic algorithm is employed to optimize the MACD parameters, tailoring the strategy to the characteristics of different stocks. To improve computational efficiency, the MindSpore framework is used for resource management and parallel computing. The optimized strategy demonstrates improved win rates, returns, Sharpe ratios, and a reduction in maximum drawdown in backtesting., Comment: 17 pages, 7 tables, and 9 figures

In this work we demonstrate a surprising way of exploitation of the mosaic--skeleton approximations for efficient numerical solving of aggregation equations with many applied kinetic kernels. The complexity of the evaluation of the right-hand side with $M$ nonlinear differential equations basing on the use of the mosaic-skeleton approximations is $\mathcal{O}(M \log^2 M)$ operations instead of $\mathcal{O}(M^2)$ for the straightforward computation. The class of kernels allowing to make fast and accurate computations via our approach is wider than analogous set of kinetic coefficients for effective calculations with previously developed algorithms. This class covers the aggregation problems arising in modelling of sedimentation, supersonic effects, turbulent flows, etc. We show that our approach makes it possible to study the systems with $M=2^{20}$ nonlinear equations within a modest computing time., Comment: 17 pages, 4 figures, 4 tables

In 1969 J. Verhoeff provided the first examples of a decimal error detecting code using a single check digit to provide protection against all single, transposition and adjacent twin errors. The three codes he presented are length 3-digit codes with 2 information digits. Existence of a 4-digit code would imply the existence of 10 such disjoint 3-digit codes. Apparently, not even a pair of such disjoint 3-digit codes is known. The code developed herein, has the property that the knowledge of any two digits is sufficient to determine the entire codeword even though their positions were unknown. This fulfills Verhoeff's desire to eliminate "cyclic errors". Phonetic errors, where 2 digit pairs of the forms X0 and 1X are interchanged, are also eliminated.

We consider the problem of learning convolution operators associated to compact Abelian groups. We study a regularization-based approach and provide corresponding learning guarantees, discussing natural regularity condition on the convolution kernel. More precisely, we assume the convolution kernel is a function in a translation invariant Hilbert space and analyze a natural ridge regression (RR) estimator. Building on existing results for RR, we characterize the accuracy of the estimator in terms of finite sample bounds. Interestingly, regularity assumptions which are classical in the analysis of RR, have a novel and natural interpretation in terms of space/frequency localization. Theoretical results are illustrated by numerical simulations.

In 1976, Knuth and Yao presented an algorithm for sampling from a finite distribution using flips of a fair coin that on average used the optimal number of flips. Here we show how to easily run their algorithm for the special case of rolling a fair die that uses memory linear in the input. Analysis of this algorithm yields a bound on the average number of coin flips needed that is slightly better than the original Knuth-Yao bound. This can then be extended to discrete distributions in a near optimal number of flips again using memory linear in the input., Comment: 11 pages, 2 figures

Regularization is a widely recognized technique in mathematical optimization. It can be used to smooth out objective functions, refine the feasible solution set, or prevent overfitting in machine learning models. Due to its simplicity and robustness, the gradient descent (GD) method is one of the primary methods used for numerical optimization of differentiable objective functions. However, GD is not well-suited for solving $\ell^1$ regularized optimization problems since these problems are non-differentiable at zero, causing iteration updates to oscillate or fail to converge. Instead, a more effective version of GD, called the proximal gradient descent employs a technique known as soft-thresholding to shrink the iteration updates toward zero, thus enabling sparsity in the solution. Motivated by the widespread applications of proximal GD in sparse and low-rank recovery across various engineering disciplines, we provide an overview of the GD and proximal GD methods for solving regularized optimization problems. Furthermore, this paper proposes a novel algorithm for the proximal GD method that incorporates a variable step size. Unlike conventional proximal GD, which uses a fixed step size based on the global Lipschitz constant, our method estimates the Lipschitz constant locally at each iteration and uses its reciprocal as the step size. This eliminates the need for a global Lipschitz constant, which can be impractical to compute. Numerical experiments we performed on synthetic and real-data sets show notable performance improvement of the proposed method compared to the conventional proximal GD with constant step size, both in terms of number of iterations and in time requirements., Comment: 20 pages, 8 figures, 1 table; To be published in journal: "MANU Contributions, Section of Natural, Mathematical and Biotechnical Sciences"

This paper is devoted to an intrinsic geometrical classification of three-mirror telescopes. The problem is formulated as the study of the connected components of a semi-algebraic set. Under first order approximation, we give the general expression of the transfer matrix of a reflexive optical system. Thanks to this representation, we express the semi-algebraic set for focal telescopes and afocal telescopes as the set of non-degenerate real solutions of first order optical conditions. Then, in order to study the topology of these sets, we address the problem of counting and describe their connected components. In a same time, we introduce a topological invariant which encodes the topological features of the solutions. For systems composed of three mirrors, we give the semi-algebraic description of the connected components of the set and show that the topological invariant is exact., Comment: 31 pages,7 figures

Algebraic methods applied to the reconstruction of Sparse-view Computed Tomography (CT) can provide both a high image quality and a decrease in the dose received by patients, although with an increased reconstruction time since their computational costs are higher. In our work, we present a new algebraic implementation that obtains an exact solution to the system of linear equations that models the problem and based on single-precision floating-point arithmetic. By applying Out-Of-Core (OOC) techniques, the dimensions of the system can be increased regardless of the main memory size and as long as there is enough secondary storage (disk). These techniques have allowed to process images of 768 x 768 pixels. A comparative study of our method on a GPU using both single-precision and double-precision arithmetic has been carried out. The goal is to assess the single-precision arithmetic implementation both in terms of time improvement and quality of the reconstructed images to determine if it is sufficient to consider it a viable option. Results using single-precision arithmetic approximately halves the reconstruction time of the double-precision implementation, whereas the obtained images retain all internal structures despite having higher noise levels., Comment: 22 pages, 12 figures, 9 tables

We consider the problem of optimizing the parameter of a two-stage algorithm for approximate solution of a system of linear algebraic equations with a sparse $n\times n$-matrix, i.e., with one in which the number of nonzero elements is $m\!=\!O(n)$. The two-stage algorithm uses conjugate gradient method at its stages. At the 1st stage, an approximate solution with accuracy $\varepsilon_1$ is found for zero initial vector. All numerical values used at this stage are represented as single-precision numbers. The obtained solution is used as initial approximation for an approximate solution with a given accuracy $\varepsilon_2$ that we obtain at the 2nd stage, where double-precision numbers are used. Based on the values of some matrix parameters, computed in a time not exceeding $O(m)$, we need to determine the value $\varepsilon_1$ which minimizes the total computation time at two stages. Using single-precision numbers for computations at the 1st stage is advantageous, since the execution time of one iteration will be approximately half that of one iteration at the 2nd stage. At the same time, using machine numbers with half the mantissa length accelerates the growth of the rounding error per iteration of the conjugate gradient method at the 1st stage, which entails an increase in the number of iterations performed at 2nd stage. As parameters that allow us to determine $\varepsilon_1$ for the input matrix, we use $n$, $m$, an estimate of the diameter of the graph associated with the matrix, an estimate of the spread of the matrix' eigenvalues, and estimates of its maximum eigenvalue. The optimal or close to the optimal value of $\varepsilon_1$ can be determined for matrix with such a vector of parameters using the nearest neighbor regression or some other type of regression.

Quantum computing has long promised to revolutionize the way we solve complex problems. At the same time, tensor networks are widely used across various fields due to their computational efficiency and capacity to represent intricate systems. While both technologies can address similar problems, the primary aim of this thesis is not to compare them. Such comparison would be unfair, as quantum devices are still in an early stage, whereas tensor network algorithms represent the state-of-the-art in quantum simulation. Instead, we explore a potential synergy between these technologies, focusing on how two flagship algorithms from each paradigm, the Density Matrix Renormalization Group (DMRG) and quantum annealing, might collaborate in the future. Furthermore, a significant challenge in the DMRG algorithm is identifying an appropriate tensor network representation for the quantum system under study. The representation commonly used is called Matrix Product Operator (MPO), and it is notoriously difficult to obtain for certain systems. This thesis outlines an approach to this problem using finite automata, which we apply to construct the MPO for our case study. Finally, we present a practical application of this framework through the quadratic knapsack problem (QKP). Despite its apparent simplicity, the QKP is a fundamental problem in computer science with numerous practical applications. In addition to quantum annealing and the DMRG algorithm, we implement a dynamic programming approach to evaluate the quality of our results. Our results highlight the power of tensor networks and the potential of quantum annealing for solving optimization problems. Moreover, this thesis is designed to be self-explanatory, ensuring that readers with a solid mathematical background can fully understand the content without prior knowledge of quantum mechanics., Comment: 62 pages. Bachelor's Final Thesis (score: 10/10)

Distributed learning algorithms, such as the ones employed in Federated Learning (FL), require communication compression to reduce the cost of client uploads. The compression methods used in practice are often biased, which require error feedback to achieve convergence when the compression is aggressive. In turn, error feedback requires client-specific control variates, which directly contradicts privacy-preserving principles and requires stateful clients. In this paper, we propose Compressed Aggregate Feedback (CAFe), a novel distributed learning framework that allows highly compressible client updates by exploiting past aggregated updates, and does not require control variates. We consider Distributed Gradient Descent (DGD) as a representative algorithm and provide a theoretical proof of CAFe's superiority to Distributed Compressed Gradient Descent (DCGD) with biased compression in the non-smooth regime with bounded gradient dissimilarity. Experimental results confirm that CAFe consistently outperforms distributed learning with direct compression and highlight the compressibility of the client updates with CAFe.

We present a new method for state preparation using the Unitary Vibrational Coupled-Cluster (UVCC) technique. Our approach utilizes redundancies in the Hilbert space in the direct mapping of vibrational modes into qubits. By eliminating half of the qubit controls required in the Trotterized UVCC ansatz, our method achieves up to a 50% theoretical reduction in the entangling gate count compared to other methods and up to a 28% reduction compared practically useful approaches. This improvement enhances the fidelity of UVCC state preparation, enabling more efficient and earlier implementation of complex quantum vibrational structure calculations on near-term quantum devices. We experimentally demonstrate our method on Quantinuum's H1-1 quantum hardware, achieving significantly higher fidelities for 6- and 8-qubit systems compared to existing implementations. For fault-tolerant architectures, eliminating half of the control qubits in multi-controlled rotations incurs an additional Toffoli gate overhead elsewhere in the circuit. Thus, the overall performance gain depends on the specific decomposition method used for multi-controlled gates.

Integer division instruction is generally expensive in most architectures. If the divisor is constant, the division can be transformed into combinations of several inexpensive integer instructions. This article discusses the classic round-up variant of the fast unsigned division by constants algorithm, and provides full proof of its correctness and feasibility. Additionally, a simpler variant for bounded dividends is presented., Comment: 9 pages

Seventy years on, Moessner's theorem and Moessner's process -- i.e., the additive computation of integral powers -- continue to fascinate. They have given rise to a variety of elegant proofs, to an implementation in hardware, to generalizations, and now even to a popular video, "The Moessner Miracle.'' The existence of this video, and even more its title, indicate that while the "what'' of Moessner's process is understood, its "how'' and even more its "why'' are still elusive. And indeed all the proofs of Moessner's theorem involve more complicated concepts than both the theorem and the process. This article identifies that Moessner's process implements an additive function with dynamic programming. A version of this implementation without dynamic programming (1) gives rise to a simpler statement of Moessner's theorem and (2) can be abstracted and then instantiated into related additive computations. The simpler statement also suggests a simpler and more efficient implementation to compute integral powers as well as simple additive functions to compute, e.g., Factorial numbers. It also reveals the source of -- to quote John Conway and Richard Guy -- Moessner's magic., Comment: In Proceedings PT 2024, arXiv:2412.01856

Finster and Mimram have defined a dependent type theory called CaTT, which describes the structure of omega-categories. Types in homotopy type theory with their higher identity types form weak omega-groupoids, so they are in particular weak omega-categories. In this article, we show that this principle makes homotopy type theory into a model of CaTT, by defining a translation principle that interprets an operation on the cell of an omega-category as an operation on higher identity types. We then illustrate how this translation allows to leverage several mechanisation principles that are available in CaTT, to reduce the proof effort required to derive results about the structure of identity types, such as the existence of an Eckmann-Hilton cell., Comment: 29 pages

Simulating quantum systems using classical computing equipment has been a significant research focus. This work demonstrates that circuits as large and complex as the random circuit sampling (RCS) circuits published as a part of Google's pioneering work [4-7] claiming quantum supremacy can be effectively simulated with high fidelity on classical systems commonly available to developers, using the universal quantum simulator included in the Quantum Rings SDK, making this advancement accessible to everyone. This study achieved an average linear cross-entropy benchmarking (XEB) score of 0.678, indicating a strong correlation with ideal quantum simulation and exceeding the XEB values currently reported for the same circuits today while completing circuit execution in a reasonable timeframe. This capability empowers researchers and developers to build, debug, and execute large-scale quantum circuits ahead of the general availability of low-error rate quantum computers and invent new quantum algorithms or deploy commercial-grade applications., Comment: 10 pages, 5 figures

Cryptography, derived from Greek meaning hidden writing, uses mathematical techniques to secure information by converting it into an unreadable format. While cryptography as a science began around 100 years ago, its roots trace back to ancient civilizations like Mesopotamia and Egypt. Over time, cryptography evolved from basic methods to complex systems involving number theory, such as modular arithmetic, the Euclidean algorithm, and Eulers totient function. This paper explores the link between early information hiding techniques and modern cryptographic algorithms like RSA, which use advanced number theory to secure data for billions of people. By analyzing historical methods, this study shows how the development of number theory enabled the transition from simple letter shifting ciphers, like the Caesar and Vigenere ciphers, to more sophisticated encryption methods. This evolution reflects a profound impact on daily life and the importance of number theory in protecting information., Comment: 27 pages, 6 Tables, 1 figure

Static Application Security Testing(SAST) tools are crucial for early bug detection and code quality but often generate false positives that slow development. Automating false positive mitigation is thus essential for advancing SAST tools. Past efforts use static/dynamic analysis or machine learning. The advent of Large Language Models, adept at understanding natural language and code, offers promising ways to improve the accuracy and usability of SAST tools. However, existing LLM-based methods need improvement in two key areas: first, extracted code snippets related to warnings are often cluttered with irrelevant control and data flows, reducing precision; second, critical code contexts are often missing, leading to incomplete representations that can mislead LLMs and cause inaccurate assessments. To ensure the use of precise and complete code context, thereby avoiding misguidance and enabling LLMs to reach accurate conclusions, we propose LLM4FPM. One of its core components is eCPG-Slicer, which builds an extended code property graph and extracts line-level, precise code context. Moreover, LLM4FPM incorporates FARF algorithm, which builds a file reference graph and then efficiently detects all files related to a warning in linear time, enabling eCPG-Slicer to gather complete code context across these files. We evaluate LLM4FPM on Juliet dataset, where it comprehensively outperforms the baseline, achieving an F1 score above 99% across various CWEs. LLM4FPM leverages a free, open-source model, avoiding costly alternatives and reducing inspection costs by up to $2758 per run on Juliet, with an average inspection time of 4.7 seconds per warning. Our work emphasizes the critical impact of precise and complete code context and highlights the potential of combining program analysis with LLMs, improving the quality and efficiency of software development., Comment: 21 pages

The ability to effectively upload data onto quantum states is an important task with broad applications in quantum computing. Numerous quantum algorithms heavily rely on the ability to efficiently upload information onto quantum states, without which those algorithms cannot achieve quantum advantage. In this paper, we address this challenge by proposing a method to upload a polynomial function $f(x)$ on the interval $x \in (a, b)$ onto a pure quantum state consisting of qubits, where a discretised $f(x)$ is the amplitude of this state. The preparation cost has quadratic scaling in the number of qubits $n$ and linear scaling with the degree of the polynomial $Q$. This efficiency allows the preparation of states whose amplitudes correspond to high-degree polynomials, enabling the approximation of almost any continuous function. We introduce an explicit algorithm for uploading such functions using four real polynomials that meet specific parity and boundedness conditions. We also generalize this approach to piece-wise polynomial functions, with the algorithm scaling linearly with the number of piecewise parts. Our method achieves efficient quantum circuit implementation and we present detailed gate counting and resource analysis., Comment: 17 pages, 8 figures, 2 tables

We study algorithms for approximating the spectral density of a symmetric matrix $A$ that is accessed through matrix-vector product queries. By combining a previously studied Chebyshev polynomial moment matching method with a deflation step that approximately projects off the largest magnitude eigendirections of $A$ before estimating the spectral density, we give an $\epsilon\cdot\sigma_\ell(A)$ error approximation to the spectral density in the Wasserstein-$1$ metric using $O(\ell\log n+ 1/\epsilon)$ matrix-vector products, where $\sigma_\ell(A)$ is the $\ell^{th}$ largest singular value of $A$. In the common case when $A$ exhibits fast singular value decay, our bound can be much stronger than prior work, which gives an error bound of $\epsilon \cdot ||A||_2$ using $O(1/\epsilon)$ matrix-vector products. We also show that it is nearly tight: any algorithm giving error $\epsilon \cdot \sigma_\ell(A)$ must use $\Omega(\ell+1/\epsilon)$ matrix-vector products. We further show that the popular Stochastic Lanczos Quadrature (SLQ) method matches the above bound, even though SLQ itself is parameter-free and performs no explicit deflation. This bound explains the strong practical performance of SLQ, and motivates a simple variant of SLQ that achieves an even tighter error bound. Our error bound for SLQ leverages an analysis that views it as an implicit polynomial moment matching method, along with recent results on low-rank approximation with single-vector Krylov methods. We use these results to show that the method can perform implicit deflation as part of moment matching., Comment: 78 pages, 1 figure

In this work we revisit the arithmetic and bit complexity of Hermitian eigenproblems. We first provide an analysis for the divide-and-conquer tridiagonal eigensolver of Gu and Eisenstat [GE95] in the Real RAM model, when accelerated with the Fast Multipole Method. The analysis asserts the claimed nearly-$O(n^2)$ complexity to compute a full diagonalization of a symmetric tridiagonal matrix. Combined with the tridiagonal reduction algorithm of Sch\"onhage [Sch72], it implies that a Hermitian matrix can be diagonalized deterministically in $O(n^{\omega}\log(n)+n^2\mathrm{polylog}(n/\epsilon))$ arithmetic operations, where $\omega\lesssim 2.371$ is the square matrix multiplication exponent. This improves the classic deterministic $O(n^3)$ diagonalization algorithms, and derandomizes the $ O(n^{\omega}\log^2(n/\epsilon))$ algorithm of [BGVKS, FOCS '20]. Ultimately, this has a direct application to the SVD, which is widely used as a subroutine in advanced algorithms, but its complexity and approximation guarantees are often unspecified. In finite precision, we show that Sch\"onhage's algorithm is stable in floating point using $O(\log(n/\epsilon))$ bits. Combined with the (rational arithmetic) algorithm of Bini and Pan [BP91], it provides a deterministic algorithm to compute all the eigenvalues of a Hermitian matrix in $O\left(n^{\omega}F\left(\log(n/\epsilon)\right)+n^2\mathrm{polylog}(n/\epsilon)\right)$ bit operations, where $F(b)\in\widetilde{O}(b)$ is the bit complexity of a single floating point operation on $b$ bits. This improves the best known $\widetilde{O}(n^3)$ deterministic and $O\left( n^{\omega}\log^2(n/\epsilon)F\left(\log^4(n/\epsilon)\log(n)\right)\right)$ randomized complexities. We conclude with some other useful subroutines such as computing spectral gaps, condition numbers, and spectral projectors, and few open problems.

We show that assuming the availability of the processor with variable precision arithmetic, we can compute matrix-by-matrix multiplications in $O(N^2log_2N)$ computational complexity. We replace the standard matrix-by-matrix multiplications algorithm $\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}=\begin{bmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\end{bmatrix}$ by $\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}=\Bigl\lfloor\begin{bmatrix} (A_{11}+\epsilon A_{12})(B_{11}+1/{\epsilon}B_{21})&(A_{11}+\epsilon A_{12})(B_{12}+1/{\epsilon}B_{22})\\(A_{21}+\epsilon A_{22})(B_{11}+1/{\epsilon}B_{21})&(A_{21}+\epsilon A_{22})(B_{12}+1/{\epsilon}B_{22})\end{bmatrix}\Bigr\rfloor \mod \frac{1}{\epsilon}$. The resulting computational complexity for $N\times N$ matrices can be estimated from recursive equation $T(N)=4(N/2)^2$ (multiplication of a matrix by number)+$4(N/2)^2$ (additions of matrices)+$2N^2$ (floor and modulo)+$4T(N/2)$ (recursive calls) as $O(N^2log_2N)$. The novelty of the method lies in the observation, somehow ignored by other matrix-by-matrix multiplication algorithms, that we can multiply matrix entries by non-integer numbers to improve computational complexity. In other words, while having a processor that can compute multiplications, additions, modulo and floor operations with variable precision arithmetic in $O(1)$, we can obtain a matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity. We also present a MATLAB code using VPA variable precision arithmetic emulator that can multiply matrices of size $N\times N$ using $(4log_2N+1)N^2$ variable precision arithmetic operations. This emulator uses $O(N)$ digits to run our algorithm., Comment: 16 pages, 1 table

Given a fixed arity $k \geq 2$, Min-$k$-CSP on complete instances involves a set of $n$ variables $V$ and one nontrivial constraint for every $k$-subset of variables (so there are $\binom{n}{k}$ constraints). The goal is to find an assignment that minimizes unsatisfied constraints. Unlike Max-$k$-CSP that admits a PTAS on dense or expanding instances, the approximability of Min-$k$-CSP is less understood. For some CSPs like Min-$k$-SAT, there's an approximation-preserving reduction from general to dense instances, making complete instances unique for potential new techniques. This paper initiates a study of Min-$k$-CSPs on complete instances. We present an $O(1)$-approximation algorithm for Min-2-SAT on complete instances, the minimization version of Max-2-SAT. Since $O(1)$-approximation on dense or expanding instances refutes the Unique Games Conjecture, it shows a strict separation between complete and dense/expanding instances. Then we study the decision versions of CSPs, aiming to satisfy all constraints; which is necessary for any nontrivial approximation. Our second main result is a quasi-polynomial time algorithm for every Boolean $k$-CSP on complete instances, including $k$-SAT. We provide additional algorithmic and hardness results for CSPs with larger alphabets, characterizing (arity, alphabet size) pairs that admit a quasi-polynomial time algorithm on complete instances., Comment: Appearing in ACM-SIAM Symposium on Discrete Algorithms (SODA25)

As AI systems increasingly integrate into critical societal sectors, the demand for robust privacy-preserving methods has escalated. This paper introduces Data Obfuscation through Latent Space Projection (LSP), a novel technique aimed at enhancing AI governance and ensuring Responsible AI compliance. LSP uses machine learning to project sensitive data into a latent space, effectively obfuscating it while preserving essential features for model training and inference. Unlike traditional privacy methods like differential privacy or homomorphic encryption, LSP transforms data into an abstract, lower-dimensional form, achieving a delicate balance between data utility and privacy. Leveraging autoencoders and adversarial training, LSP separates sensitive from non-sensitive information, allowing for precise control over privacy-utility trade-offs. We validate LSP's effectiveness through experiments on benchmark datasets and two real-world case studies: healthcare cancer diagnosis and financial fraud analysis. Our results show LSP achieves high performance (98.7% accuracy in image classification) while providing strong privacy (97.3% protection against sensitive attribute inference), outperforming traditional anonymization and privacy-preserving methods. The paper also examines LSP's alignment with global AI governance frameworks, such as GDPR, CCPA, and HIPAA, highlighting its contribution to fairness, transparency, and accountability. By embedding privacy within the machine learning pipeline, LSP offers a promising approach to developing AI systems that respect privacy while delivering valuable insights. We conclude by discussing future research directions, including theoretical privacy guarantees, integration with federated learning, and enhancing latent space interpretability, positioning LSP as a critical tool for ethical AI advancement., Comment: 19 pages, 6 figures, submitted to Conference ICADCML2025

We explore a robust version of the barycenter problem among $n$ centered Gaussian probability measures, termed Semi-Unbalanced Optimal Transport (SUOT)-based Barycenter, wherein the barycenter remains fixed while the others are relaxed using Kullback-Leibler divergence. We develop optimization algorithms on Bures-Wasserstein manifold, named the Exact Geodesic Gradient Descent and Hybrid Gradient Descent algorithms. While the Exact Geodesic Gradient Descent method is based on computing the exact closed form of the first-order derivative of the objective function of the barycenter along a geodesic on the Bures manifold, the Hybrid Gradient Descent method utilizes optimizer components when solving the SUOT problem to replace outlier measures before applying the Riemannian Gradient Descent. We establish the theoretical convergence guarantees for both methods and demonstrate that the Exact Geodesic Gradient Descent algorithm attains a dimension-free convergence rate. Finally, we conduct experiments to compare the normal Wasserstein Barycenter with ours and perform an ablation study., Comment: Ngoc-Hai Nguyen and Dung Le contributed equally to this work. 44 pages, 5 figures

In realistic radar tracking, target measurement uncertainty (TMU) in terms of both detection probability and measurement error covariance is significantly affected by the target-to-radar (T2R) geometry. However, existing posterior Cramer-Rao Lower Bounds (PCRLBs) rarely investigate the fundamental impact of T2R geometry on target measurement uncertainty and eventually on mean square error (MSE) of state estimate, inevitably resulting in over-conservative lower bound. To address this issue, this paper firstly derives the generalized model of target measurement error covariance for bistatic radar with moving receiver and transmitter illuminating any type of signal, along with its approximated solution to specify the impact of T2R geometry on error covariance. Based upon formulated TMU model, an improved PCRLB (IPCRLB) fully accounting for both measurement origin uncertainty and geometry-dependent TMU is then re-derived, both detection probability and measurement error covariance are treated as state-dependent parameters when differentiating log-likelihood with respect to target state. Compared to existing PCRLBs that partially or completely ignore the dependence of target measurement uncertainty on T2R geometry, proposed IPCRLB provides a much accurate (less-conservative) lower bound for radar tracking in clutter with geometry-dependent TMU. The new bound is then applied to radar trajectory control to effectively optimize T2R geometry and exhibits least uncertainty of acquired target measurement and more accurate state estimate for bistatic radar tracking in clutter, compared to state-of-the-art trajectory control methods., Comment: 15 pages,12 figures

Recent advances in federated learning have shown that asynchronous variants can be faster and more scalable than their synchronous counterparts. However, their design does not include quantization, which is necessary in practice to deal with the communication bottleneck. To bridge this gap, we develop a novel algorithm, Quantized Asynchronous Federated Learning (QAFeL), which introduces a hidden-state quantization scheme to avoid the error propagation caused by direct quantization. QAFeL also includes a buffer to aggregate client updates, ensuring scalability and compatibility with techniques such as secure aggregation. Furthermore, we prove that QAFeL achieves an $\mathcal{O}(1/\sqrt{T})$ ergodic convergence rate for stochastic gradient descent on non-convex objectives, which is the optimal order of complexity, without requiring bounded gradients or uniform client arrivals. We also prove that the cross-term error between staleness and quantization only affects the higher-order error terms. We validate our theoretical findings on standard benchmarks.

The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in Nesterov and Polyak (2006) and Cartis, Gould and Toint (2011) to require, under standard assumptions, at most $\mathcal{O}(\epsilon^{3/(3-q)})$ evaluations of the objective function and its derivatives of degrees one and two to produce an $\epsilon$-approximate critical point of order $q\in\{1,2\}$. This bound was shown to be sharp for $q \in\{1,2\}$. This note revisits these results and shows that the example for which slow convergence is exhibited is not isolated, but that this behaviour occurs for a subset of univariate functions of nonzero measure., Comment: 11 pages, 1 figure

This paper introduces the Stable Matching Based Pairing (SMBP) algorithm, a high-performance external validity index for clustering evaluation in large-scale datasets with a large number of clusters. SMBP leverages the stable matching framework to pair clusters across different clustering methods, significantly reducing computational complexity to $O(N^2)$, compared to traditional Maximum Weighted Matching (MWM) with $O(N^3)$ complexity. Through comprehensive evaluations on real-world and synthetic datasets, SMBP demonstrates comparable accuracy to MWM and superior computational efficiency. It is particularly effective for balanced, unbalanced, and large-scale datasets with a large number of clusters, making it a scalable and practical solution for modern clustering tasks. Additionally, SMBP is easily implementable within machine learning frameworks like PyTorch and TensorFlow, offering a robust tool for big data applications. The algorithm is validated through extensive experiments, showcasing its potential as a powerful alternative to existing methods such as Maximum Match Measure (MMM) and Centroid Ratio (CR)., Comment: 16 pages, 14 tables

Wakefield acceleration methods are known due to some their advantages. The main of them is the high accelerating gradient up to several teravolts per meter. In the paper another important advantage is concluded to the possibility of using a wakefield accelerator as a source of electrons by means of obtaining self injected bunches and their accelera-tion. The result is the simulation of the process of plasma wakefield excitation by a laser pulse with an energy of tens of mJ and a power of 1-2 TW for obtaining the promising electron source. Homogeneous and Gaussian plasma profiles were investigated and compared to increase the energy of the self-injected bunches. The laser parameters were taken that corresponded to the parameters of the laser setup in the Institute of Plasma Electronics and New Methods of Acceleration of the National Scientific Center "Kharkiv Institute of Physics and Technology". Based on the results of the simulation, the possibility of obtaining relativistic self-injected bunches that can be used for further laser acceler-ation experiments, including dielectric laser acceleration, was demonstrated., Comment: 6 pages, 10 figures, 5 tables

The mean squared error and regularized versions of it are standard loss functions in supervised machine learning. However, calculating these losses for large data sets can be computationally demanding. Modifying an approach of J. Dick and M. Feischl [Journal of Complexity 67 (2021)], we present algorithms to reduce extensive data sets to a smaller size using rank-1 lattices. Rank-1 lattices are quasi-Monte Carlo (QMC) point sets that are, if carefully chosen, well-distributed in a multidimensional unit cube. The compression strategy in the preprocessing step assigns every lattice point a pair of weights depending on the original data and responses, representing its relative importance. As a result, the compressed data makes iterative loss calculations in optimization steps much faster. We analyze the errors of our QMC data compression algorithms and the cost of the preprocessing step for functions whose Fourier coefficients decay sufficiently fast so that they lie in certain Wiener algebras or Korobov spaces. In particular, we prove that our approach can lead to arbitrary high convergence rates as long as the functions are sufficiently smooth., Comment: 25 pages, 1 figure

The efficiency of exact subset sum problem algorithms which compute individual subset sums is defined as $e=min(T/z, 1)$, where $z$ is the number of subset sums computed. $e$ is related to these algorithms' computational complexity. This system maps the sums into $kn$ bins to select its most efficient algorithm for each bin for each input value. These algorithms include additive, subtractive and repeated value dynamic programming. Cases which would otherwise be processed inefficiently (eg: all even values) are handled by modular arithmetic and by dynamically partioning the input values. The system's experimentally validated efficiency corresponds to O(max($T$, $n^2$)) with space complexity O(max($T$, $n$)), for $k=2$., Comment: 10 pages

Robots find extensive applications in industry. In recent years, the influence of robots has also increased rapidly in domestic scenarios. The Q-learning algorithm aims to maximise the reward for reaching the goal. This paper proposes a modified version of the Q-learning algorithm, known as Q-learning with scaled distance metric (Q-SD). This algorithm enhances task learning and makes task completion more meaningful. A robotic manipulator (agent) applies the Q-SD algorithm to the task of table cleaning. Using Q-SD, the agent acquires the sequence of steps necessary to accomplish the task while minimising the manipulator's movement distance. We partition the table into grids of different dimensions. The first has a grid count of 3 times 3, and the second has a grid count of 4 times 4. Using the Q-SD algorithm, the maximum success obtained in these two environments was 86% and 59% respectively. Moreover, Compared to the conventional Q-learning algorithm, the drop in average distance moved by the agent in these two environments using the Q-SD algorithm was 8.61% and 6.7% respectively., Comment: 9 pages, 9 figures, 7 tables

This article introduces 'cpp11armadillo', a new R package that integrates the powerful Armadillo C++ library for linear algebra into the R programming environment. Targeted primarily at social scientists and other non-programmers, this article explains the computational benefits of moving code to C++ in terms of speed and syntax. We provide a comprehensive overview of Armadillo's capabilities, highlighting its user-friendly syntax akin to MATLAB and its efficiency for computationally intensive tasks. The 'cpp11armadillo' package simplifies a part of the process of using C++ within R by offering additional ease of integration for those who require high-performance linear algebra operations in their R workflows. This work aims to bridge the gap between computational efficiency and accessibility, making advanced linear algebra operations more approachable for R users without extensive programming backgrounds., Comment: 23 pages, 0 figures

We revisit the standard ``telescoping sum'' argument ubiquitous in the final steps of analyzing evaluation complexity of algorithms for smooth nonconvex optimization, and obtain a refined formulation of the resulting bound as a function of the requested accuracy $\epsilon$. While bounds obtained using the standard argument typically are of the form $\mathcal{O}(\epsilon^{-\alpha})$ for some positive $\alpha$, the refined results are of the form $o(\epsilon^{-\alpha})$. We then explore to which known algorithms our refined bounds are applicable and finally describe an example showing how close the standard and refined bounds can be., Comment: 10 ages, 1 figure

The main goal of this paper is to propose a new quaternion total variation regularization model for solving linear ill-posed quaternion inverse problems, which arise from three-dimensional signal filtering or color image processing. The quaternion total variation term in the model is represented by collaborative total variation regularization and approximated by a quaternion iteratively reweighted norm. A novel flexible quaternion generalized minimal residual method is presented to quickly solve this model. An improved convergence theory is established to obtain a sharp upper bound of the residual norm of quaternion minimal residual method (QGMRES). The convergence theory is also presented for preconditioned QGMRES. Numerical experiments indicate the superiority of the proposed model and algorithms over the state-of-the-art methods in terms of iteration steps, CPU time, and the quality criteria of restored color images., Comment: 26 pages, 2 figures, 4 tables

Solving very large linear systems of equations is a key computational task in science and technology. In many cases, the coefficient matrix of the linear system is rank-deficient, leading to systems that may be underdetermined, inconsistent, or both. In such cases, one generally seeks to compute the least squares solution that minimizes the residual of the problem, which can be further defined as the solution with smallest norm in cases where the coefficient matrix has a nontrivial nullspace. This work presents several new techniques for solving least squares problems involving coefficient matrices that are so large that they do not fit in main memory. The implementations include both CPU and GPU variants. All techniques rely on complete orthogonal decompositions that guarantee that both conditions of a least squares solution are met, regardless of the rank properties of the matrix. Specifically, they rely on the recently proposed "randUTV" algorithm that is particularly effective in strongly communication-constrained environments. A detailed precision and performance study reveals that the new methods, that operate on data stored on disk, are competitive with state-of-the-art methods that store all data in main memory., Comment: 26 pages, 12 figures

We study the parameterized complexity of algorithmic problems whose input is an integer set $A$ in terms of the doubling constant $C := |A + A|/|A|$, a fundamental measure of additive structure. We present evidence that this new parameterization is algorithmically useful in the form of new results for two difficult, well-studied problems: Integer Programming and Subset Sum. First, we show that determining the feasibility of bounded Integer Programs is a tractable problem when parameterized in the doubling constant. Specifically, we prove that the feasibility of an integer program $I$ with $n$ polynomially-bounded variables and $m$ constraints can be determined in time $n^{O_C(1)} poly(|I|)$ when the column set of the constraint matrix has doubling constant $C$. Second, we show that the Subset Sum and Unbounded Subset Sum problems can be solved in time $n^{O_C(1)}$ and $n^{O_C(\log \log \log n)}$, respectively, where the $O_C$ notation hides functions that depend only on the doubling constant $C$. We also show the equivalence of achieving an FPT algorithm for Subset Sum with bounded doubling and achieving a milestone result for the parameterized complexity of Box ILP. Finally, we design near-linear time algorithms for $k$-SUM as well as tight lower bounds for 4-SUM and nearly tight lower bounds for $k$-SUM, under the $k$-SUM conjecture. Several of our results rely on a new proof that Freiman's Theorem, a central result in additive combinatorics, can be made efficiently constructive. This result may be of independent interest., Comment: 24 pages, 0 figures

We propose an experimental study of adaptive time-stepping methods for efficient modeling of the aggregation-fragmentation kinetics. Precise modeling of this phenomena usually requires utilization of the large systems of nonlinear ordinary differential equations and intensive computations. We concentrate on performance of three explicit Runge-Kutta time-integration methods and provide simulations for two types of problems: finding of equilibrium solutions and simulations for kinetics with periodic solutions. The first class of problems may be analyzed through the relaxation of the solution to the stationary state after large time. In this case, the adaptive time-stepping may help to reach it using big steps reducing cost of the calculations without loss of accuracy. In the second case, the problem becomes numerically unstable at certain points of the phase space and may require tiny steps making the simulations very time-consuming. Adaptive criteria allows to increase the steps for most of points and speedup simulations significantly., Comment: 9 pages, 3 figures, 3 tables

In this manuscript we present a novel and efficient numerical method for the compressible viscous and resistive MHD equations for all Mach number regimes. The time-integration strategy is a semi-implicit splitting, combined with a hybrid finite-volume and finite-element (FE) discretization in space. The non-linear convection is solved by a robust explicit FV scheme, while the magneto-acoustic terms are treated implicitly in time. The resulting CFL stability condition depends only on the fluid velocity, and not on the Alfv\'enic and acoustic modes. The magneto-acoustic terms are discretized by compatible FE based on a continuous and a discrete de Rham complexes designed using Finite Element Exterior Calculus (FEEC). Thanks to the use of FEEC, energy stability, magnetic-helicity conservation and the divergence-free conditions can be preserved also at the discrete level. A very efficient splitting approach is used to separate the acoustic and the Alfv\'enic modes in such a fashion that the original symmetries of the PDE governing equations are preserved. In this way, the algorithm relies on the solution of linear, symmetric and positive-definite algebraic systems, that are very efficiently handled by the simple matrix-free conjugate-gradient method. The resulting algorithm showed to be robust and accurate in low and high Mach regimes even at large Courant numbers. Non-trivial tests are solved in one-, two- and three- space dimensions to confirm the robustness, accuracy, and the low-dissipative and conserving properties of the final algorithm. While the formulation of the method is very general, numerical results for a second-order accurate FV-FE scheme will be presented., Comment: 46 pages, 18 figures, 3 tables

Gaussian random fields play an important role in many areas of science and engineering. In practice, they are often simulated by sampling from a high-dimensional multivariate normal distribution, which arises from the discretisation of a suitable precision operator. Existing methods such as Cholesky factorization and Gibbs sampling become prohibitively expensive on fine meshes due to their high computational cost. In this work, we revisit the Multigrid Monte Carlo (MGMC) algorithm developed by Goodman & Sokal (Physical Review D 40.6, 1989) in the quantum physics context. To show that MGMC can overcome these issues, we establish a grid-size-independent convergence theory based on the link between linear solvers and samplers for multivariate normal distributions, drawing on standard multigrid convergence theory. We then apply this theory to linear Bayesian inverse problems. This application is achieved by extending the standard multigrid theory to operators with a low-rank perturbation. Moreover, we develop a novel bespoke random smoother which takes care of the low-rank updates that arise in constructing posterior moments. In particular, we prove that Multigrid Monte Carlo is algorithmically optimal in the limit of the grid-size going to zero. Numerical results support our theory, demonstrating that Multigrid Monte Carlo can be significantly more efficient than alternative methods when applied in a Bayesian setting., Comment: 57 pages, 4 figures, 1 table; submitted to "Foundations of Computational Mathematics"

Complex reflection groups comprise a generalization of Weyl groups of semisimple Lie algebras, and even more generally of finite Coxeter groups. They have been heavily studied since their introduction and complete classification in the 1950s by Shephard and Todd, due to their many applications to combinatorics, representation theory, knot theory, and mathematical physics, to name a few examples. For each given complex reflection group G, we explain a new recipe for producing an integrable system of linear differential equations whose differential Galois group is precisely G. We exhibit these systems explicitly for many (low-rank) irreducible complex reflection groups in the Shephard-Todd classification.

A fully stochastic second-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}(\epsilon^{-3/2})$ complexity bound for finding first-order critical points. The method is noise-tolerant and the inexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative evaluation is inexact and to minimization of finite sums by sampling are discussed. Numerical experiments on large binary classification problems illustrate the potential of the new method., Comment: 32 pages, 9 figures

Dual Coordinate Descent (DCD) and Block Dual Coordinate Descent (BDCD) are important iterative methods for solving convex optimization problems. In this work, we develop scalable DCD and BDCD methods for the kernel support vector machines (K-SVM) and kernel ridge regression (K-RR) problems. On distributed-memory parallel machines the scalability of these methods is limited by the need to communicate every iteration. On modern hardware where communication is orders of magnitude more expensive, the running time of the DCD and BDCD methods is dominated by communication cost. We address this communication bottleneck by deriving $s$-step variants of DCD and BDCD for solving the K-SVM and K-RR problems, respectively. The $s$-step variants reduce the frequency of communication by a tunable factor of $s$ at the expense of additional bandwidth and computation. The $s$-step variants compute the same solution as the existing methods in exact arithmetic. We perform numerical experiments to illustrate that the $s$-step variants are also numerically stable in finite-arithmetic, even for large values of $s$. We perform theoretical analysis to bound the computation and communication costs of the newly designed variants, up to leading order. Finally, we develop high performance implementations written in C and MPI and present scaling experiments performed on a Cray EX cluster. The new $s$-step variants achieved strong scaling speedups of up to $9.8\times$ over existing methods using up to $512$ cores.

We give a construction in a column of a one-dimensional cellular automaton of the Minkowski sum of two sets which can themselves occur in columns of cellular automata. It enables us to obtain another construction of the set of integers that are sums of three squares, answering a question by the same author., Comment: In Proceedings GASCom 2024, arXiv:2406.14588

A parametric class of trust-region algorithms for constrained nonconvex optimization is analyzed, where the objective function is never computed. By defining appropriate first-order stationarity criteria, we are able to extend the Adagrad method to the newly considered problem and retrieve the standard complexity rate of the projected gradient method that uses both the gradient and objective function values. Furthermore, we propose an additional iteration-dependent scaling with slightly inferior theoretical guarantees. In both cases, the bounds are essentially sharp, and curvature information can be used to compute the stepsize. Initial experimental results for noisy bound-constrained instances illustrate the benefits of the objective-free approach.

We present a theoretical framework for the analysis of amplitude transfer in Quantum Variational Algorithms (QVAs) for combinatorial optimisation with mixing unitaries defined by vertex-transitive graphs, based on their continuous-time quantum walk (CTQW) representation and the theory of graph automorphism groups. This framework leads to a heuristic for designing efficient problem-specific QVAs. Using this heuristic, we develop novel algorithms for unconstrained and constrained optimisation. We outline their implementation with polynomial gate complexity and simulate their application to the parallel machine scheduling and portfolio rebalancing combinatorial optimisation problems, showing significantly improved convergence over preexisting QVAs. Based on our analysis, we derive metrics for evaluating the suitability of graph structures for specific problem instances, and for establishing bounds on the convergence supported by different graph structures. For mixing unitaries characterised by a CTQW over a Hamming graph on $m$-tuples of length $n$, our results indicate that the amplification upper bound increases with problem size like $\mathcal{O}(e^{n \log m})$.

We present a version of the sieve of Eratosthenes that can factor all integers $\le x$ in $O(x \log\log x)$ arithmetic operations using at most $O(\sqrt{x}/\log\log x)$ bits of space. This is an improved space bound under the condition that the algorithm takes at most $O(x\log\log x)$ time. We also show our algorithm performs well in practice.