More Like this

1. Lp quasi-norm minimization: algorithm and applications

   https://doi.org/10.1186/s13634-024-01114-6  

   Sleem, Omar M. ; Ashour, M. E. ; Aybat, N. S. ; Lagoa, Constantino M. ( February 2024 , EURASIP Journal on Advances in Signal Processing)

   Sparsity finds applications in diverse areas such as statistics, machine learning, and signal processing. Computations over sparse structures are less complex compared to their dense counterparts and need less storage. This paper proposes a heuristic method for retrieving sparse approximate solutions of optimization problems via minimizing the$$\ell _{p}$$${\ell }_p$quasi-norm, where$$0$0<p<1$. An iterative two-block algorithm for minimizing the$$\ell _{p}$$${\ell }_p$quasi-norm subject to convex constraints is proposed. The proposed algorithm requires solving for the roots of a scalar degree polynomial as opposed to applying a soft thresholding operator in the case of$$\ell _{1}$$${\ell }_1$norm minimization. The algorithm’s merit relies on its ability to solve the$$\ell _{p}$$${\ell }_p$quasi-norm minimization subject to any convex constraints set. For the specific case of constraints defined by differentiable functions with Lipschitz continuous gradient, a second, faster algorithm is proposed. Using a proximal gradient step, we mitigate the convex projection step and hence enhance the algorithm’s speed while proving its convergence. We present various applications where the proposed algorithm excels, namely, sparse signal reconstruction, system identification, and matrix completion. The results demonstrate the significant gains obtained by the proposed algorithm compared to other$$\ell _{p}$$${\ell }_p$quasi-norm based methods presented in previous literature.

    

   more » « less
2. On the stationarity for nonlinear optimization problems with polyhedral constraints

   https://doi.org/10.1007/s10107-023-01979-9  

   di Serafino, Daniela ; Hager, William W. ; Toraldo, Gerardo ; Viola, Marco ( May 2023 , Mathematical Programming)

   For polyhedral constrained optimization problems and a feasible point$$\textbf{x}$$$x$, it is shown that the projection of the negative gradient on the tangent cone, denoted$$\nabla _\varOmega f(\textbf{x})$$${\nabla }_{\Omega }f\left(x\right)$, has an orthogonal decomposition of the form$$\varvec{\beta }(\textbf{x}) + \varvec{\varphi }(\textbf{x})$$$\beta \left(x\right)+\phi \left(x\right)$. At a stationary point,$$\nabla _\varOmega f(\textbf{x}) = \textbf{0}$$${\nabla }_{\Omega }f\left(x\right)=0$so$$\Vert \nabla _\varOmega f(\textbf{x})\Vert $$$\Vert {\nabla }_{\Omega }f\left(x\right)\Vert$reflects the distance to a stationary point. Away from a stationary point,$$\Vert \varvec{\beta }(\textbf{x})\Vert $$$\Vert \beta \left(x\right)\Vert$and$$\Vert \varvec{\varphi }(\textbf{x})\Vert $$$\Vert \phi \left(x\right)\Vert$measure different aspects of optimality since$$\varvec{\beta }(\textbf{x})$$$\beta \left(x\right)$only vanishes when the KKT multipliers at$$\textbf{x}$$$x$have the correct sign, while$$\varvec{\varphi }(\textbf{x})$$$\phi \left(x\right)$only vanishes when$$\textbf{x}$$$x$is a stationary point in the active manifold. As an application of the theory, an active set algorithm is developed for convex quadratic programs which adapts the flow of the algorithm based on a comparison between$$\Vert \varvec{\beta }(\textbf{x})\Vert $$$\Vert \beta \left(x\right)\Vert$and$$\Vert \varvec{\varphi }(\textbf{x})\Vert $$$\Vert \phi \left(x\right)\Vert$.

    

   more » « less
3. Random-Cluster Dynamics on Random Regular Graphs in Tree Uniqueness

   https://doi.org/10.1007/s00220-021-04093-z  

   Blanca, Antonio ; Gheissari, Reza ( April 2021 , Communications in Mathematical Physics)

   We establish rapid mixing of the random-cluster Glauber dynamics on random$$\varDelta $$$\Delta$-regular graphs for all$$q\ge 1$$$q\ge 1$and$$p$p<p_u(q,\Delta )$, where the threshold$$p_u(q,\varDelta )$$$p_u(q,\Delta )$corresponds to a uniqueness/non-uniqueness phase transition for the random-cluster model on the (infinite)$$\varDelta $$$\Delta$-regular tree. It is expected that this threshold is sharp, and for$$q>2$$$q>2$the Glauber dynamics on random$$\varDelta $$$\Delta$-regular graphs undergoes an exponential slowdown at$$p_u(q,\varDelta )$$$p_u(q,\Delta )$. More precisely, we show that for every$$q\ge 1$$$q\ge 1$,$$\varDelta \ge 3$$$\Delta \ge 3$, and$$p$p<p_u(q,\Delta )$, with probability$$1-o(1)$$$1-o\left(1\right)$over the choice of a random$$\varDelta $$$\Delta$-regular graph onnvertices, the Glauber dynamics for the random-cluster model has$$\varTheta (n \log n)$$$\Theta (nlogn)$mixing time. As a corollary, we deduce fast mixing of the Swendsen–Wang dynamics for the Potts model on random$$\varDelta $$$\Delta$-regular graphs for every$$q\ge 2$$$q\ge 2$, in the tree uniqueness region. Our proof relies on a sharp bound on the “shattering time”, i.e., the number of steps required to break up any configuration into$$O(\log n)$$$O(logn)$sized clusters. This is established by analyzing a delicate and novel iterative scheme to simultaneously reveal the underlying random graph with clusters of the Glauber dynamics configuration on it, at a given time.

    

   more » « less
4. Random Quantum Circuits Transform Local Noise into Global White Noise

   https://doi.org/10.1007/s00220-024-04958-z  

   Dalzell, Alexander M. ; Hunter-Jones, Nicholas ; Brandão, Fernando G. S. L. ( March 2024 , Communications in Mathematical Physics)

   We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gate-level error with probability close to one. We model noise by adding a pair of weak, unital, single-qubit noise channels after each two-qubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution$$p_{\text {noisy}}$$$p_{\text{noisy}}$and the corresponding noiseless output distribution$$p_{\text {ideal}}$$$p_{\text{ideal}}$shrink exponentially with the expected number of gate-level errors. Specifically, the linear cross-entropy benchmarkFthat measures this correlation behaves as$$F=\text {exp}(-2s\epsilon \pm O(s\epsilon ^2))$$$F=\text{exp}(-2sϵ\pm O\left(s{ϵ}^2\right))$, where$$\epsilon $$$ϵ$is the probability of error per circuit location andsis the number of two-qubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution$$p_{\text {noisy}}$$$p_{\text{noisy}}$and the uniform distribution$$p_{\text {unif}}$$$p_{\text{unif}}$decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as$$p_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1-F)p_{\text {unif}}$$$p_{\text{noisy}}\approx F{p}_{\text{ideal}}+(1-F)p_{\text{unif}}$. In other words, although at least one local error occurs with probability$$1-F$$$1-F$, the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by$$O(F\epsilon \sqrt{s})$$$O\left(Fϵ\sqrt{s}\right)$. Thus, the “white-noise approximation” is meaningful when$$\epsilon \sqrt{s} \ll 1$$$ϵ\sqrt{s}\ll 1$, a quadratically weaker condition than the$$\epsilon s\ll 1$$$ϵs\ll 1$requirement to maintain high fidelity. The bound applies if the circuit size satisfies$$s \ge \Omega (n\log (n))$$$s\ge \Omega (nlog(n\left)\right)$, which corresponds to onlylogarithmic depthcircuits, and if, additionally, the inverse error rate satisfies$$\epsilon ^{-1} \ge {\tilde{\Omega }}(n)$$${ϵ}^{-1}\ge \tilde{\Omega }\left(n\right)$, which is needed to ensure errors are scrambled faster thanFdecays. The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; for example, it was an underlying assumption in complexity-theoretic arguments that noisy random quantum circuits cannot be efficiently sampled classically, even when the fidelity is low. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds.

    

   more » « less
5. Spherical convex hull of random points on a wedge

   https://doi.org/10.1007/s00208-023-02704-9  

   Besau, Florian ; Gusakova, Anna ; Reitzner, Matthias ; Schütt, Carsten ; Thäle, Christoph ; Werner, Elisabeth M. ( August 2023 , Mathematische Annalen)

   Consider two half-spaces$$H_1^+$$$H_1^{+}$and$$H_2^+$$$H_2^{+}$in$${\mathbb {R}}^{d+1}$$$R^{d+1}$whose bounding hyperplanes$$H_1$$$H_1$and$$H_2$$$H_2$are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$$S_{2,+}^d:=S^d\cap H_1^{+}\cap H_2^{+}$is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$$S^d$, which contains a great subsphere of dimension$$d-2$$$d-2$and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$$S_{2,+}^d$and consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$$\log n$$$logn$. A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {S}}_{2,+}^d$$$S_{2,+}^d$. The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a half-sphere.

    

   more » « less