Information Theory · Cross-listed from eess.SP
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Wednesday 15 April
This paper investigates the uplink capacity of single-input single-output (SISO) systems assisted by a swarm of network-controlled repeaters (NCRs). We develop a rigorous wideband formulation based on OFDM signaling. Starting from the continuous-time passband model, we derive the capacity expression for the repeater-assisted OFDM channel, accounting for amplified noise contributions from multiple repeaters. Numerical results demonstrate that NCRs can substantially enhance system capacity even with simple activation strategies, and that activating only the closest repeater yields nearly the same performance as activating all repeaters, thereby offering significant energy-saving opportunities. These findings highlight the potential of NCR swarms as a cost-effective and scalable solution for coverage extension and capacity enhancement in wideband wireless networks.
Dynamical Systems
On the Rokhlin lemma for infinite measure-preserving bijections
We study the Rokhlin lemma in the context of infinite measure-preserving bijections, and completely classify such bijections up to $\lambda$-approximate conjugacy, where $\lambda$ is the infinite measure which is preserved. This sharpens the classical version of the Rokhlin lemma, which only provides such a classification up to $\mu$-approximate conjugacy where $\mu$ is a probability measure equivalent to $\lambda$.
Read the full abstract
Geometric Topology
All knots are trivial: a "proof" by sleight of hand
We take a close look at a classical magic trick performed with a string, where a trivial knot is seemingly isotoped into a trefoil, and generalize it to a family of magic tricks for transforming the unknot into other knots. We encode such a trick by depicting the target knot as a special type of knot diagram, which we call a "knotholder diagram". By proving that all knots admit knotholder diagrams, we obtain variants of the trick for producing every knot.
Read the full abstract
Probability · Cross-listed from q-fin.PR
Higher-order ATM asymptotics for the CGMY model via the characteristic function
Using only the characteristic function, we derive short-time at-the-money (ATM) call-price asymptotics for the exponential CGMY model with activity parameter $Y\in(1,2)$. The Lipton–Lewis formula expresses the normalized ATM call price, denoted $c(t,0)$, in terms of the characteristic exponent, which, upon rescaling at the rate $t^{-1/Y}$ from the $Y$-stable domain of attraction, yields $c(t,0) = d_{1} t^{1/Y} + d_{2} t + o(t)$ as $t\downarrow 0$. The first-order coefficient $d_{1}$ is the known stable limit from the domain of attraction of a symmetric $Y$-stable law, and $d_{2}$ is given by an explicit integral involving the characteristic exponent and the limiting stable exponent. We then extract closed-form higher-order coefficients by keeping the full Lipton–Lewis integrand intact and introducing a dynamic cutoff that partitions the domain into inner, core, and tail regions, establishing the expansion with controlled remainder. All coefficients are verified numerically against existing closed-form expressions where available.
Read the full abstract
Combinatorics · Cross-listed from econ.TH
Balanced Contributions in Networks and Games with Externalities
For networks with externalities, where each component's worth may depend on the full network structure, balanced contributions and fairness lead to distinct component-efficient allocation rules. We characterize the unique component-efficient allocation rule satisfying balanced contributions – the BCE rule. Existence is the main challenge: balanced contributions must hold on every edge, but the construction uses only spanning-tree edges. A cycle-sum identity bridges this gap by reducing balanced contributions on non-tree edges to relations in proper subnetworks. The BCE rule coincides with the Myerson value for TU games and with its generalization by Jackson–Wolinsky for network games without externalities, it recovers the externality-free value on the complete network, and – unlike the fairness-based FCE rule – it does not reduce to a graph-free formula applied to the graph-restricted game.
Read the full abstract
Mathematical Physics · Cross-listed from cond-mat.mtrl-sci
Spatial deformation of a ferromagnetic elastic rod
Ferromagnetic elastic slender structures offer the potential for large actuation displacements under modest external magnetic fields, due to the magneto-mechanical coupling. This paper investigates the phase portraits of the Hamiltonian governing the three-dimensional deformation of inextensible ferromagnetic elastic rods subjected to combined terminal tension and twisting moment in the presence of a longitudinal magnetic field. The total energy functional is formulated by combining the Kirchhoff elastic strain energy with micromagnetic energy contributions appropriate to soft and hard ferromagnetic materials: magnetostatic (demagnetization) energy for the former, and exchange and Zeeman energies for the latter. Exploiting the circular cross-sectional symmetry and the integrable structure of the governing equations, conserved Casimir invariants are identified and the Hamiltonian is reduced to a single-degree-of-freedom system in the Euler polar angle. Analysis of the resulting phase portraits reveals that purely elastic and hard ferromagnetic rods undergo a supercritical Hamiltonian Hopf pitchfork bifurcation, whereas soft ferromagnetic rods exhibit this bifurcation only within a restricted range of the magnetoelastic parameter, $0<\tilde{K}_{dM}<1/8$. Both helical and localized post-buckling configurations are analyzed, and the corresponding load-deformation relationships are systematically characterized across a range of loading scenarios. Localized buckling modes, corresponding to homoclinic orbits in the Hamiltonian phase space, are constructed numerically. In contrast to the purely elastic case, the localized configurations of soft ferromagnetic rods exhibit non-collinear extended straight segments, a geometrically distinctive feature arising directly from the magnetoelastic coupling.
Read the full abstract
Numerical Analysis
Pathwise convergence of a linearization scheme for stochastic differential-algebraic equations under the local Lipschitz coefficients
The paper deals with the numerical treatment of index-1 stochastic differential-algebraic equations (SDAEs) with nonlinear coefficients that satisfy the local Lipschitz and the Khasminskii conditions. The key challenge here is the presence of a singular and non-autonomous matrix in the equation, which makes the numerical method challenging to analyze. To tackle this challenge, we develop a more general numerical method using a local linearization technique. More precisely, we use the Taylor expansion to decompose locally the drift component of the SDAEs in linear and nonlinear parts. The linear part is approximated implicitly and must resolve the singularity issue of each time step, while the nonlinear part is approximated explicitly. This method is fascinating due to the fact that it is efficient in high dimension. We prove that this novel numerical method converges in the pathwise sense with rate $\frac{1}{2}-\epsilon$, for arbitrary $\epsilon >0$. The implementation of this novel numerical method is also carried out to verify our theoretical result.
Read the full abstract
Mathematical Physics · Cross-listed from nlin.SI
On the discrete Painlevé equivalence problem, non-conjugate translations and nodal curves
We consider several examples of nonautonomous systems of difference equations coming from semi-classical orthogonal polynomials via recurrence coefficients and ladder operators, with respect to various generalisations of Laguerre and Meixner weights. We identify these as discrete Painlevé equations and establish their types in the Sakai classification scheme in terms of the associated rational surfaces. In particular, we find examples which come from different weights and share a common surface type $D_5^{(1)}$ but are inequivalent in two ways. First, their dynamics are generated by non-conjugate elements of $\widehat{W}(A_3^{(1)})$. Second, some of the examples have associated surfaces being non-generic in the sense of having nodal curves. The symmetries of these examples form subgroups of the generic symmetry group, which we compute. In particular, we find $(W(A_1^{(1)})\times W(A_1^{(1)}))\rtimes \mathbb{Z}/2\mathbb{Z}$. These examples give further weight to the argument that any correspondence between different weights and the Sakai classification should make use of the refined version of the discrete Painlevé equivalence problem, which takes into account not just surface type, but also the group elements generating the dynamics as well as parameter constraints, e.g. those corresponding to nodal curves.
Read the full abstract
Mathematical Physics
On Exponentially Long Prethermalization Timescales in Isolated Quantum Systems
We study prethermalization in time-independent quantum many-body systems on a $d$-dimensional lattice with an extensive local Hamiltonian $H=N+\varepsilon P$, in the regime where $\varepsilon \ll 1$. We prove that the prethermal timescale is exponential in $\varepsilon_0/\varepsilon$, where $\varepsilon_0$ is an explicit scale determined by the locality exponent and the local norm of $P$. We also construct two extensive local quasi-conserved quantities whose variation remains exponentially small throughout this time interval.
Read the full abstract
Statistics Theory
The Integer-valued Moving-Average Random Field
An integer-valued moving average (INMA) model for count random fields is proposed and investigated. Closed-form expressions are derived for both its marginal distribution and spatial dependence structure, for arbitrary model order and also covering the multilateral case. In particular, general expressions for bivariate distributions and autocovariances are provided. It is shown that the INMA random field can be equipped (among others) with a Poisson marginal distribution. It is also demonstrated that different and well-interpretable dependence structures are possible. For illustration, we discuss a real-world data example and propose an INMA approximation to a given spatial dependence structure.
Read the full abstract
Differential Geometry
Several new $SL(2,Z)$ modular forms and anomaly cancellation formulas
In \cite{HLZ2} and \cite{HHLZ}, using $E_8$ bundles, some modular forms over $SL(2,{\bf Z})$ were constructed on $12$-dimensional manifolds and the Witten-Freed-Hopkins anomaly cancellation formula was derived by these $SL(2,Z)$ modular forms. In this paper, we construct several similar $SL(2,Z)$ modular forms on any dimensional manifolds and some new anomaly cancellation formulas and applications are given.
Read the full abstract
Analysis of PDEs
Optimal constant for the trace inequality in $BV$ for domains with corners
We determine the explicit value of the optimal constant in the trace inequality for functions of bounded variations in the case the domain has a particular class of singularities.
Analysis of PDEs
On the anisotropic critical $p$-Laplace equation: classification, decomposition, and stability results
We investigate both qualitative and quantitative issues related to the classification of non-negative energy solutions to the anisotropic critical $p$-Laplace equation in $\mathbb{R}^n$, for $1<p<n$. Specifically, we establish an anisotropic version of Struwe's decomposition, along with the interaction estimate for the family of bubbles in this decomposition. Moreover, we provide a short proof of the classification result as well as a quantitative stability result, proving that every energy solution to a perturbation of the anisotropic critical equation must be closed to a bubble, in the absence of bubbling.
Read the full abstract
Numerical Analysis
A representation and comparison of three cubic macro-elements
The paper is concerned with three types of cubic splines over a triangulation that are characterized by three degrees of freedom associated with each vertex of the triangulation. The splines differ in computational complexity, polynomial reproduction properties, and smoothness. With the aim to make them a versatile tool for numerical analysis, a unified representation in terms of locally supported basis functions is established. The construction of these functions is based on geometric concepts and is expressed in the Bernstein–Bézier form. They are readily applicable in a range of standard approximation methods, which is demonstrated by a number of numerical experiments.
Read the full abstract
Algebraic Topology
Relating Brauer categories, Koszul complexes, and graph complexes
The purpose of this paper is to investigate the relationship between hairy graph complexes associated to cyclic operads and their counterparts for operads (and, more generally, dioperads). This is based on the author's interpretation of these as Koszul complexes for the associated modules over the respective appropriate twisted downward (walled) Brauer category. The general question of relating such Koszul complexes is addressed by analysing the relationships between the respective twisted Brauer-type categories, proceeding through a direct analysis. The passage from the walled to unwalled context involves functors induced by the disjoint union of finite sets. As an application, for the cyclic operad associated to an operad, this leads to an explicit relation between the respective (hairy) graph homologies.
Read the full abstract
Group Theory
Cohomology of the pure symmetric automorphisms of right-angled Artin groups
We compute the cohomology groups of the pure symmetric outer automorphism group $\Sigma$POut$(A_\Gamma)$ and the pure symmetric automorphism group $\Sigma$PAut$(A_\Gamma)$ of a right-angled Artin group $A_\Gamma$. Using the equivariant spectral sequence arising from the action of $\Sigma$POut$(A_\Gamma)$ on the generalized McCullough-Miller complex MM$_\Gamma$, we show that $H^q(\Sigma$POut$(A_\Gamma))$ is free abelian and we compute its rank in terms of the combinatorics of certain poset. Applying the Lyndon-Hochschild-Serre spectral sequence and the Leray-Hirsch theorem we do the same for $H^q(\Sigma$PAut$(A_\Gamma))$. In both cases the cohomology ring is generated in degree 1. Finally, we introduce the Generalized Brownstein-Lee Conjecture, proposing a presentation of $H^*(\Sigma$PAut$(A_\Gamma))$, and prove that it holds in dimension $2$.
Read the full abstract
Information Theory · Cross-listed from eess.SP
Network-Controlled Repeaters Under Power Amplifier Non-linearities
Network-controlled repeaters (NCRs) are a low-cost means to extend coverage and strengthen macro diversity in wireless networks. They operate in real time by amplifying and re-transmitting the incoming signal with only hardware-level delays, without requiring any channel state information (CSI) at the repeater itself. However, their power amplifiers (PAs) generate non-linear distortion that is jointly forwarded with the desired signal and can undermine multiuser performance unless the distortion statistics are exploited. This paper develops a distortion-aware (DA) uplink framework for repeater-assisted massive MIMO (RA-MIMO) under PA non-linearities. We adopt a memoryless third-order polynomial model for the repeater PA and characterize the achievable spectral efficiency (SE) using the Bussgang decomposition. Closed-form expressions are derived for the Bussgang gain matrix and the distortion covariance. We also design a DA combining vector that maximizes the effective signal-to-interference-plus-distortion ratio.
Read the full abstract
Analysis of PDEs
Local and global minimality of the lamella for the anisotropic Ohta-Kawasaki energy
In this paper we consider the volume-constrained minimization of a variant of the Ohta-Kawasaki functional with an anisotropic surface energy replacing the standard perimeter. Following and suitably adapting the second variation approach devised in arXiv:1211.0164, we prove local minimality results for the horizontal lamellar configuration, in analogy with the isotropic case, under the assumption that the anisotropy is uniformly elliptic. If instead the Wulff shape of the anisotropy has upper and lower horizontal facets, we prove that the lamella exhibits a rigid behavior and is an isolated local minimizer for all parameter values. We conclude by showing some global minimality results, mostly focusing on the planar case.
Read the full abstract
Differential Geometry
Constrained Curvature Flows on Pinched Hadamard Surfaces
We study area- and length-preserving curvature flows for embedded closed curves on pinched Hadamard surfaces. In the variable-curvature setting, the evolution equations contain additional lower-order terms, so the PDE analysis requires refined comparison arguments and delicate curvature estimates. For smooth convex initial curves, we prove preservation and instantaneous strictness of convexity, long-time existence, and uniform bounds for the curvature and its higher derivatives. Under additional geometric assumptions, we obtain convergence of the curvature to a constant. In the rotationally symmetric case, the area-preserving flow exhibits a dichotomy: either the evolving curves converge exponentially to a geodesic circle, or they drift off to infinity and approach a constant-curvature limit curve. We also identify a geometric condition on the initial curve that prevents escape to infinity and guarantees convergence to a geodesic circle.
Read the full abstract
Analysis of PDEs
A note on Sobolev inequalities in the lower limit case
We study Poincare-Sobolev type inequalities for compactly supported smooth functions which are defined in the Euclidean $n$-space and whose absolute value of gradient are Choquet $\delta /n$-integrable with respect to the $\delta$-dimensional Hausdorff content, $n\geq 2$, $\delta\in (0,n]$. In particular, our results imply a new Sobolev inequality for quasicontinuous functions defined in the Sobolev space $W^{1,1}_0(\mathbb{R}^n)$. As an application we extend a recently introduced superlevel Sobolev inequality into a context of the Hausdorff content.
Read the full abstract
Optimization and Control
Sum-of-Squares Stability Verification on Manifolds with Applications in Spacecraft Attitude Control
In the context of spacecraft attitude control, parametrizations such as direction vectors or quaternions are often used to avoid singularities in the attitude representation. This, however, complicates the stability analysis of the system since, given the additional unit constraints, the resulting dynamics evolve on non-contractible manifolds. In this paper, we present a framework to verify almost global asymptotic stability of such systems using LaSalle's invariance principle and sum-of-squares programming, simplifying the search for Lyapunov functions. The framework is then applied to two examples: two-axis attitude acquisition utilizing aerodynamics in very low Earth orbits, and three-axis attitude acquisition for a satellite subject to gravity gradient torques in a circular orbit.
Read the full abstract
Combinatorics
A local spectral condition for perfect matchings in 3-graphs
Let $\gamma$ be a constant such that $0 < \gamma < 1$, and let $n$ be a sufficiently large integer. Consider a $3$-uniform hypergraph $H$ on $n$ vertices. In 2013, Kühn, Osthus, and Treglown, along with Khan independently, proved that for large enough $n$ with $n\equiv 0\pmod{3}$, if $\delta_1(H)\geq\binom{2n/3}{2}$, then $H$ admits a perfect matching. For any vertex $v\in V(H)$, we define $N_H(v)$ as the $2$-graph with vertex set $V(H)\setminus\{v\}$ and edge set $E(N_H(v)) = \{e\subseteq V(H)\setminus\{v\}: e\cup \{v\}\in E(H)\}$. In this paper, we show that if $\rho(N_H(v)) > (2/3+\gamma)n$ for all $v\in V(H)$, where $\rho(N_H(v))$ denotes the spectral radius of $N_H(v)$, then $H$ has a perfect matching. This bound is asymptotically tight. Furthermore, for integer $s$ satisfying $n\geq 3s+3$, we establish that if \[ \rho(N_H(v))>\frac{1}{2}(s-1+\sqrt{(s-1)^2+4s(n-s-1)})\] holds for every $v\in V(H),$ then $H$ admits a fractional matching of size $s+1$. Notably, this second spectral bound is tight.
Read the full abstract
Analysis of PDEs
Green's Function and Pointwise Space-time Behaviors of the three-Dimensional modified Vlasov-Poisson-Boltzmann System
The pointwise space-time behavior of the Green's function of the three-dimensional modified Vlasov-Poisson-Boltzmann system is studied in this paper. It is shown that the Green's function has a decomposition of the macroscopic diffusive waves and Huygens waves with the speed $\sqrt{\frac{8}{3}}$ at low-frequency, the singular kinetic wave and the remainder term decaying exponentially in space and time. In addition, we establish the pointwise space-time estimate of the global solution to the nonlinear modified Vlasov-Poisson-Boltzmann system based on the Green's function.
Read the full abstract
Dynamical Systems
Bound on the number of Ruelle resonances for Gevrey hyperbolic flows
We improve the best known upper bounds on the number of Ruelle resonances in disks of large radius for Gevrey uniformly hyperbolic flows. The proof is based on Rugh's approach of dynamical determinants that replaces the study of the flow itself by the analysis of a system of open hyperbolic maps.
Read the full abstract
Combinatorics
Openly disjoint cycles and directed tree-width of regular digraphs
Given a digraph $D$, let $c(D)$ denote the largest integer $k$ such that there are $k$ openly disjoint cycles through a vertex, i.e., a collection of directed cycles $C_1,\ldots,C_k$ through a common vertex $v$ such that $C_1-v,\ldots,C_k-v$ are pairwise vertex-disjoint. The famous Caccetta-Häggkvist conjecture and its regular variant due to Behzad, Chartrand and Wall from 1970, have motivated the study of degree conditions forcing $c(D)$ to be large. In 1985 Thomassen constructed digraphs of arbitrarily high minimum out- and in-degree such that $c(D)\le 2$. In 2005, Seymour asked whether in contrast every $r$-regular digraph satisfies $c(D)=r$, which would have implied the Behzad-Chartrand-Wall conjecture. In 2008, Mader answered this negatively for every $r\ge 8$, but conjectured that nevertheless the minimum value $c_r$ of $c(D)$ over all $r$-regular digraphs grows with $r$, i.e. $\lim_{r\rightarrow\infty}c_r=\infty$. As the first main result of our paper, we prove Mader's conjecture in a strong form by showing $c_r\ge \lceil\frac{3}{22} r\rceil$ for every $r\in \mathbb{N}$. We also show $c_r\le 7\left\lceil \frac{r}{8}\right\rceil$, improving the previous best upper bound $c_r\le r-\Theta(\sqrt{r})$ due to Mader. In our second main result we show that every $r$-regular digraph has directed tree-width $\Omega(r)$. This is tight up to the implied constant and cannot be extended to digraphs of minimum out- and in-degree at least $r$. As a corollary we obtain the existence of a function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that every regular digraph with degree at least $f(k)$ contains a subdivision of the cylindrical wall of order $k$, and hence of a large class of planar digraphs. This makes progress on the notoriously difficult problem of finding degree conditions guaranteeing subdivisions of digraphs, related to a well-known conjecture of Mader from 1985.
Read the full abstract
Representation Theory
Global dimension of dg algebras via compact silting objects
We introduce a notion of global dimension for a triangulated category relative to a compact silting object. We prove that the finiteness of this dimension is an intrinsic property of the triangulated category itself and, therefore, independent of the choice of the silting object. Focusing on the setup of connective differential graded (dg) algebras, we analyse the behaviour of global dimension under dg algebra homomorphisms and establish explicit bounds. This allows us to deduce a bound for the global dimension of certain dg quiver algebras. We also relate the regularity of the big singularity category of a proper connective dg algebra to the finiteness of its global dimension.
Read the full abstract
Information Theory
Towards Autonomous Driving with Short-Packet Rate Splitting: Age of Information Analysis and Optimization
To address the high mobility impacts and the ultra-reliable and low-latency communication (URLLC) requirements in autonomous driving scenarios, rate-splitting multiple access (RSMA) combined with short-packet communication (SPC) emerges as a promising solution.Autonomous vehicles rely on real-time information exchange to ensure safety and coordination, making information freshness essential.By jointly capturing transmission delays and packet errors, age of information (AoI) serves as a comprehensive metric for freshness.In this paper, we investigate short-packet rate splitting to enhance information freshness measured by the AoI.By splitting the unicast messages into common and private parts, encoding all common parts together with the multicast message into a common stream, and encoding each private part into a private stream, RSMA effectively manages interference and enables achieving lower AoI.By considering critical factors such as transmit power, vehicle velocity, blocklength, and the number of transmit antennas, we derive closed-form expressions for the average AoI (AAoI) of the common stream under partial decoding and the overall AAoI under complete decoding.To enhance the AAoI performance, we propose the multi-start two-step successive convex approximation (SCA) algorithm.This algorithm first optimizes the power allocation and subsequently optimizes the rate splitting under the quality of service (QoS) trade-off constraint.Simulation results demonstrate that our short-packet rate-splitting scheme significantly improves the AAoI performance while ensuring system fairness and enabling ultra-low AAoI through the common stream, meeting the requirements of autonomous driving applications.Moreover, the trade-off between the common and overall performance is revealed, indicating that the overall performance can be further enhanced while maintaining the advantages of the common stream.
Read the full abstract
Probability
node2vec or triangle-biased random walks: stationarity, regularity & recurrence
The node2vec random walk is a non-Markovian random walk on the vertex set of a graph, widely used for network embedding and exploration. This random walk model is defined in terms of three parameters which control the probability of, respectively, backtracking moves, moves within triangles, and moves to the remaining neighboring nodes. From a mathematical standpoint, the node2vec random walk is a nontrivial generalization of the non-backtracking random walk and thus belongs to the class of second-order Markov chains. Despite its widespread use in applications, little is known about its long-run behavior. The goal of this paper is to begin exploring its fundamental properties on arbitrary graphs. To this aim, we show how lifting the node2vec random walk to the state spaces of directed edges and directed wedges yields two distinct Markovian representations which are key for its asymptotic analysis. Using these representations, we find mild sufficient conditions on the underlying finite or infinite graph to guarantee ergodicity, reversibility, recurrence and characterization of the invariant measure. As we discuss, the behavior of the node2vec random walk is drastically different compared to the non-backtracking random walk. While the latter simplifies on arbitrary graphs when using its natural edge Markovian representation thanks to bistochasticity, the former simplifies on regular graphs when using its natural wedge Markovian representation. Remarkably, this representation reveals that a graph is regular if and only if a certain weighted Eulerianity condition holds.
Read the full abstract
Information Theory
Scalable Design for RIS-Assisted Multi-User Downlink System Empowered by RSMA under Partial CSI
In large-scale reconfigurable intelligent surface (RIS) communication systems, the precise acquisition of channel state information (CSI) is challenging. Consider a practical RIS configuration where only a few reflective elements serve as anchors to estimate CSI, which are termed partial CSI. To improve the robustness against partial CSI and the scalability of RIS networks, this paper proposes an unsupervised learning-based rate-splitting multiple access (RSMA) scheme for RIS-assisted multi-user systems. Specifically, RISnet, a neural network architecture designed to infer full CSI from partial observations, is employed and integrated with a low-complexity RSMA precoder. Effective channel features are constituted from partial CSI, and the original elements with channel information contribute to new anchors after expansion in RISnet. Numerical results demonstrate that the proposed scheme approximates the performance with a full CSI of RIS under deterministic raytracing channel conditions. When channel uncertainty increases during training, RSMA has been shown to enhance RISnet robustness, significantly mitigating performance loss.
Read the full abstract
Information Theory
Weighted Riemannian Optimization for Solving Quadratic Equations from Gaussian Magnitude Measurements
This paper explores the problem of generalized phase retrieval, which involves reconstructing a length-$n$ signal $\bm{x}$ from its $m$ phaseless samples $y_k = \left|\langle \bm{a}_k,\bm{x}\rangle\right|^2$, where $k = 1,2,...,m$, and $\bm{a}_k$ are the measurement vectors. This problem can be reformulated into recovering a positive semidefinite rank-$1$ matrix $\bm{X}=\bm{x}\bm{x}^*$ from linear samples $\bm{y}=\mathcal{A}(\bm{X})\in\mathbb{R}^m$, thereby requiring us to find a rank-$1$ solution of the linear equations. We demonstrate that several existing phase retrieval algorithms, including Wirtinger Flow (WF) and the canonical Riemannian gradient descent (RGD), actually solve the least-squares fitting of this linear equation on the Riemannian manifold of rank-$1$ matrices, but utilize different metrics on this manifold. Nevertheless, these metrics only allow for a stable and far-apart-from-isometric embedding of rank-$1$ matrices to $\mathbb{R}^m$ by $\mathcal{A}$, resulting in a linear convergence with a considerably large convergence factor. To expedite the convergence, we establish a new metric on the rank-$1$ matrix manifold that facilitates the nearly isometric embedding of rank-$1$ matrices into $\mathbb{R}^m$ through $\mathcal{A}$. A RGD algorithm under this new metric, termed Weighted RGD (WRGD), is proposed to tackle the phase retrieval problem. Owing to the near isometry, we prove that our WRGD algorithm, initialized by spectral methods, can linearly converge to the underlying signal $\bm{x}$ with a small convergence factor. Empirical experiments strongly validate the efficiency and resilience of our algorithms compared to the truncated Wirtinger Flow (TWF) algorithm and the canonical RGD algorithm.