The generalized two-dimensional fractional sine transform (2D-FrST) is a powerful analytic instrument for the spectral analysis of bivariate signals that arise in multi-scale supply-chain dynamics, hybrid-vehicle systems and resilient logistics networks. In this paper we state and rigorously prove Modulation Theorem-2, which expresses the 2D-FrST of a function modulated by a product of cosines (or by mixed sine–cosine factors) as a linear combination of four fractional sine or cosine transforms evaluated at frequency points shifted by the modulation frequencies. We further establish the Shifting Property, showing that a spatial translation of the original function maps, under the 2D-FrST, into a linear combination of fractional sine and cosine transforms of a phase-modulated version of the function. Both results are derived by means of elementary product-to-sum and angle-addition identities together with a careful accounting of the quadratic-phase factors that appear in the fractional kernel. The theoretical developments are illustrated by concrete applications to artificial-intelligence pattern mining and blockchain-based immutable logging, thereby enhancing transparency, traceability and resilience of digital supply-chain ecosystems. All results are placed in the broader context of the FKF-transform framework and related spectral methods recently introduced for multi-echelon lead-time analysis and secure logistics networks. Keywords— generalized two-dimensional fractional sine transform; modulation theorem; shifting property; fractional cosine transform; AI–blockchain integration; supply-chain resilience; FKF transform; spectral analysis; transparency; traceability.
Haihan Zhang, Chenheng Zhang, Zhiquan Qi, Zhouchen Lin
Whether exact scalar feedback intrinsically incurs the additional dimension $d$ paid by known zeroth-order methods remains open even for Lipschitz convex optimization. For a universal Lipschitz scale, the value only bound $O(d^2\log(d+1)\log(1/ε))$ and two-point bound $O(dε^{-2})$ yield the upper bound $\widetilde O\left(d\min\{d,ε^{-2}\}\right)$. By contrast, prior lower bounds for arbitrary randomized algorithms give only $Ω(\min\{d,ε^{-2}\})$, leaving a factor $d$ unexplained. We close this gap, up to logarithmic factors, for arbitrary adaptive randomized algorithms minimizing a convex objective with a universal Lipschitz scale over the $d$-dimensional Euclidean unit ball, where each query returns only the exact scalar value. Let $T_ε$ denote the minimum number of queries required to return an $ε$-suboptimal point with probability at least $1/2$, uniformly over the function class. We prove that \[T_ε\ge c\,\frac{d\min\{d,ε^{-2}\}}{\log\!\bigl(\min\{d,ε^{-2}\}\bigr)},\] for $d\ge d_0$ and $0<ε\leε_0$, where $c,ε_0>0$ and $d_0\in\mathbb N$ are universal constants. This gives $Ω\left(\frac{d}{ε^2\log(1/ε)}\right)$ in the low-accuracy regime $ε\ge d^{-1/2}$ and $Ω\left(\frac{d^2}{\log d}\right)$ in the high-accuracy regime $ε\le d^{-1/2}$ with the latter independent of $ε$. These bounds match the corresponding upper bound up to logarithmic factors. To our knowledge, this is the first near-optimal lower bound for arbitrary adaptive randomized algorithms throughout both accuracy regimes of exact value Lipschitz convex optimization. The proof uses a random support function hard family and develops a posterior mean energy method for adaptive exact max observations, in place of first-order zero chain constructions and noise based transcript inequalities.
Giovanni Seraghiti, Kévin Dubrulle, Arnaud Vandaele, Nicolas Gillis
Nonnegative matrix factorization (NMF) approximates a nonnegative matrix, $X$, by the product of two nonnegative factors, $WH$, where $W$ has $r$ columns and $H$ has $r$ rows. In this paper, we consider NMF using the component-wise L1 norm as the error measure (L1-NMF), which is suited for data corrupted by heavy-tailed noise, such as Laplace noise or salt and pepper noise, or in the presence of outliers. Our first contribution is an NP-hardness proof for L1-NMF, even when $r=1$, in contrast to the standard NMF that uses least squares. Our second contribution is to show that L1-NMF strongly enforces sparsity in the factors for sparse input matrices, thereby favoring interpretability. However, if the data is affected by false zeros, too sparse solutions might degrade the model. Our third contribution is a new, more general, L1-NMF model for sparse data, dubbed weighted L1-NMF (wL1-NMF), where the sparsity of the factorization is controlled by adding a penalization parameter to the entries of $WH$ associated with zeros in the data. The fourth contribution is a new coordinate descent (CD) approach for wL1-NMF, denoted as sparse CD (sCD), where each subproblem is solved by a weighted median algorithm. To the best of our knowledge, sCD is the first algorithm for L1-NMF whose complexity scales with the number of nonzero entries in the data, making it efficient in handling large-scale, sparse data. We perform extensive numerical experiments on synthetic and real-world data to show the effectiveness of our new proposed model (wL1-NMF) and algorithm (sCD).
Di Wang, Xiangyu Guo, Chaowen Guan, Shi Li · 5 authors
Recently, many machine learning and statistical models such as non-linear regressions, the Single Index, Multi-index, Varying Coefficient Index Models and Two-layer Neural Networks can be reduced to or be seen as a special case of a new model which is called the \textit{Stochastic Linear Combination of Non-linear Regressions} model. However, due to the high non-convexity of the problem, there is no previous work study how to estimate the model. In this paper, we provide the first study on how to estimate the model efficiently and scalably. Specifically, we first show that with some mild assumptions, if the variate vector $x$ is multivariate Gaussian, then there is an algorithm whose output vectors have $\ell_2$-norm estimation errors of $O(\sqrt{\frac{p}{n}})$ with high probability, where $p$ is the dimension of $x$ and $n$ is the number of samples. The key idea of the proof is based on an observation motived by the Stein's lemma. Then we extend our result to the case where $x$ is bounded and sub-Gaussian using the zero-bias transformation, which could be seen as a generalization of the classic Stein's lemma. We also show that with some additional assumptions there is an algorithm whose output vectors have $\ell_\infty$-norm estimation errors of $O(\frac{1}{\sqrt{p}}+\sqrt{\frac{p}{n}})$ with high probability. We also provide a concrete example to show that there exists some link function which satisfies the previous assumptions. Finally, for both Gaussian and sub-Gaussian cases we propose a faster sub-sampling based algorithm and show that when the sub-sample sizes are large enough then the estimation errors will not be sacrificed by too much. Experiments for both cases support our theoretical results. To the best of our knowledge, this is the first work that studies and provides theoretical guarantees for the stochastic linear combination of non-linear regressions model.
Chaining, i.e., the mode of operation in which each message is encrypted considering a digital summary of previous ones, is here applied to block-cipher stages based on compressed sensing. We show that this simple and parsimonious technique may significantly harden the resulting system with respect to common threats such that ciphertext-only, known-plaintext, and man-in-the-middle attacks. Non-negligible robustness comes at the price of not more than a 2% of energy overhead with respect to the pure compression stage which represents a 24× reduction with respect to straightforward implementation of a traditional cryptography primitive like Advanced Encryption Standard.
Jayakrishnan Unnikrishnan, Saeid Haghighatshoar, Martin Vetterli
We study the problem of solving a linear sensing system when the observations are unlabeled. Specifically we seek a solution to a linear system of equations y = Ax when the order of the observations in the vector y is unknown. Focusing on the setting in which A is a random matrix with i.i.d. entries, we show that if the sensing matrix A admits an oversampling ratio of 2 or higher, then, with probability 1, it is possible to recover x exactly without the knowledge of the order of the observations in y. Furthermore, if x is of dimension K, then any 2K entries of y are sufficient to recover x. This result implies the existence of deterministic unlabeled sensing matrices with an oversampling factor of 2 that admit perfect reconstruction. The result is universal in that conditioned on the realization of matrix A, recovery is guaranteed for all possible choices of x. While the proof is constructive, it uses a combinatorial algorithm which is not practical, leaving the question of complexity open. We also analyze a noisy version of the problem and show that local stability is guaranteed by the solution. In particular, for every x, the recovery error tends to zero as the signal-to-noise ratio tends to infinity. The question of universal stability is unclear. In addition, we obtain a converse of the result in the noiseless case: If the number of observations in y is less than 2K, then with probability 1, universal recovery fails, i.e., with probability 1, there exist distinct choices of x which lead to the same unordered list of observations in y. We also present extensions of the result of the noiseless case to special cases with non-i.i.d. entries in A, and to a different setting in which the labels of a portion of the observations y are known. In terms of applications, the unlabeled sensing problem is related to data association problems encountered in different domains including robotics where it is appears in a method called “simultaneous localization and mapping”, multi-target tracking applications, and in sampling signals in the presence of jitter.
Open access
Sparse and Compressive Sensing Techniques
Distributed Sensor Networks and Detection Algorithms
We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. As demonstrated heuristically and numerically by Krzakala et al. \cite{KrzakalaEtAl}, message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements with undersampling rates close to the fraction of non-zero coordinates. We use an approximate message passing (AMP) algorithm and analyze it through the state evolution method. We give a rigorous proof that this approach is successful as soon as the undersampling rate $δ$ exceeds the (upper) Rényi information dimension of the signal, $\uRenyi(p_X)$. More precisely, for a sequence of signals of diverging dimension $n$ whose empirical distribution converges to $p_X$, reconstruction is with high probability successful from $\uRenyi(p_X)\, n+o(n)$ measurements taken according to a band diagonal matrix. For sparse signals, i.e., sequences of dimension $n$ and $k(n)$ non-zero entries, this implies reconstruction from $k(n)+o(n)$ measurements. For `discrete' signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from $o(n)$ measurements. The result is robust with respect to noise, does not apply uniquely to random signals, but requires the knowledge of the empirical distribution of the signal $p_X$.
Open access
2 source records
Sparse and Compressive Sensing Techniques
Microwave Imaging and Scattering Analysis
Distributed Sensor Networks and Detection Algorithms
For the general problem of minimizing a convex function over a compact convex domain, we will investigate a simple iterative approximation algorithm based on the method by Frank & Wolfe 1956, that does not need projection steps in order to stay inside the optimization domain. Instead of a projection step, the linearized problem defined by a current subgradient is solved, which gives a step direction that will naturally stay in the domain. Our framework generalizes the sparse greedy algorithm of Frank & Wolfe and its primal-dual analysis by Clarkson 2010 (and the low-rank SDP approach by Hazan 2008) to arbitrary convex domains. We give a convergence proof guaranteeing ε-small duality gap after O(1/ε) iterations. The method allows us to understand the sparsity of approximate solutions for any l1-regularized convex optimization problem (and for optimization over the simplex), expressed as a function of the approximation quality. We obtain matching upper and lower bounds of Θ(1/ε) for the sparsity for l1-problems. The same bounds apply to low-rank semidefinite optimization with bounded trace, showing that rank O(1/ε) is best possible here as well. As another application, we obtain sparse matrices of O(1/ε) non-zero entries as ε-approximate solutions when optimizing any convex function over a class of diagonally dominant symmetric matrices. We show that our proposed first-order method also applies to nuclear norm and max-norm matrix optimization problems. For nuclear norm regularized optimization, such as matrix completion and low-rank recovery, we demonstrate the practical efficiency and scalability of our algorithm for large matrix problems, as e.g. the Netflix dataset. For general convex optimization over bounded matrix max-norm, our algorithm is the first with a convergence guarantee, to the best of our knowledge.