A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z  

  Subjects -> ELECTRONICS (Total: 207 journals)
The end of the list has been reached or no journals were found for your choice.
Similar Journals
Journal Cover
IEEE Transactions on Information Theory
Journal Prestige (SJR): 1.162
Citation Impact (citeScore): 3
Number of Followers: 28  
 
  Hybrid Journal Hybrid journal (It can contain Open Access articles)
ISSN (Print) 0018-9448
Published by IEEE Homepage  [228 journals]
  • IEEE Transactions on Information Theory publication information

    • Free pre-print version: Loading...

      Abstract: Presents a listing of the editorial board, board of governors, current staff, committee members, and/or society editors for this issue of the publication.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • IEEE Transactions on Information Theory information for authors

    • Free pre-print version: Loading...

      Abstract: These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Quadratically Constrained Myopic Adversarial Channels

    • Free pre-print version: Loading...

      Authors: Yihan Zhang;Shashank Vatedka;Sidharth Jaggi;Anand D. Sarwate;
      Pages: 4901 - 4948
      Abstract: We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most $2log (n)$ bits in one sub-regime, and at most $Omega ({n})$ bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Entropic Compressibility of Lévy Processes

    • Free pre-print version: Loading...

      Authors: Julien Fageot;Alireza Fallah;Thibaut Horel;
      Pages: 4949 - 4963
      Abstract: In contrast to their seemingly simple and shared structure of independence and stationarity, Lévy processes exhibit a wide variety of behaviors, from the self-similar Wiener process to piecewise-constant compound Poisson processes. Inspired by the recent paper of Ghourchian, Amini, and Gohari, we characterize their compressibility by studying the entropy of their double discretization (both in time and amplitude) in the regime of vanishing discretization steps. For a Lévy process with absolutely continuous marginals, this reduces to understanding the asymptotics of the differential entropy of its marginals at small times, for which we obtain a new local central limit theorem. We generalize known results for stable processes to the non-stable case, with a special focus on Lévy processes that are locally self-similar, and conceptualize a new compressibility hierarchy of Lévy processes, captured by their Blumenthal–Getoor index.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Resolution Limits of Non-Adaptive 20 Questions Search for Multiple Targets

    • Free pre-print version: Loading...

      Authors: Lin Zhou;Lin Bai;Alfred O. Hero;
      Pages: 4964 - 4982
      Abstract: We study the problem of simultaneous search for multiple targets over a multidimensional unit cube and derive fundamental resolution limits of non-adaptive querying procedures using the 20 questions estimation framework. The performance criterion that we consider is the achievable resolution, which is defined as the maximal $L_infty $ norm between the location vector and its estimated version where the maximization is over all target location vectors. The fundamental resolution limit is defined as the minimal achievable resolution of any non-adaptive query procedure, where each query has binary yes/no answers. We drive non-asymptotic and second-order asymptotic bounds on the minimal achievable resolution, using tools from finite blocklength information theory. Specifically, in the achievability part, we relate the 20 questions problem to data transmission over a multiple access channel, use the information spectrum method by Han and borrow results from finite blocklength analysis for random access channel coding. In the converse part, we relate the 20 questions problem to data transmission over a point-to-point channel and adapt finite blocklength converse results for channel coding. Our results extend the purely first-order asymptotic analyses of Kaspi et al. (ISIT 2015) for the one-dimensional case: we consider channels beyond the binary symmetric channel and derive non-asymptotic and second-order asymptotic bounds on the performance of optimal non-adaptive query procedures.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Improved Bounds for (b, k)-Hashing

    • Free pre-print version: Loading...

      Authors: Stefano Della Fiore;Simone Costa;Marco Dalai;
      Pages: 4983 - 4997
      Abstract: For fixed integers $n$ and $bgeq k$ , let $A(b,k,n)$ the largest size of a subset of ${1,2,ldots,b}^{n}$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. Bounding $A(b,k,n)$ is a problem of relevant interest in information theory and computer science, relating to the zero-error capacity with list decoding and to the study of $(b, k)$ -hash families of functions. It is known that, for fixed $b$ and $k$ , $A(b,k,n)$ grows exponentially in $n$ . In this paper, we determine new exponential upper bounds for different values of $b$ and $k$ . A first bound on $A(b,k,n)$ for general $b$ and $k$ was derived by Fredman and Komlós in the ’80s and improved for certain $bneq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for general $b$ and $k$ by Guruswami and Riazanov, while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan, and by Costa and Dalai. In this paper, we strengthen the bounds for some specific values of $b$ and $k$ . Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinite-dimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Asymptotics of Sequential Composite Hypothesis Testing Under Probabilistic
           Constraints

    • Free pre-print version: Loading...

      Authors: Jiachun Pan;Yonglong Li;Vincent Y. F. Tan;
      Pages: 4998 - 5012
      Abstract: We consider the sequential composite binary hypothesis testing problem in which one of the hypotheses is governed by a single distribution while the other is governed by a family of distributions whose parameters belong to a known set $Gamma $ . We would like to design a test to decide which hypothesis is in effect. Under the constraints that the probabilities that the length of the test, a stopping time, exceeds $n$ are bounded by a certain threshold $epsilon $ , we obtain certain fundamental limits on the asymptotic behavior of the sequential test as $n$ tends to infinity. Assuming that $Gamma $ is a convex and compact set, we obtain the set of all first-order error exponents for the problem. We also prove a strong converse. Additionally, we obtain the set of second-order error exponents under the assumption that the alphabet of the observations $mathcal {X}$ is finite. In the proof of second-order asymptotics, a main technical contribution is the derivation of a central limit-type result for a maximum of an uncountable set of log-likelihood ratios under suitable conditions. This result may be of independent interest. We also show that some important statistical models satisfy the conditions.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • A Strengthened Cutset Upper Bound on the Capacity of the Relay Channel and
           Applications

    • Free pre-print version: Loading...

      Authors: Abbas El Gamal;Amin Gohari;Chandra Nair;
      Pages: 5013 - 5043
      Abstract: We develop a new upper bound on the capacity of the relay channel that is tighter than previously known upper bounds. This upper bound is proved using traditional weak converse techniques involving mutual information inequalities and Gallager-type explicit identification of auxiliary random variables. We show that the new upper bound is strictly tighter than all previous bounds for the Gaussian relay channel with non-zero channel gains. When specialized to the relay channel with orthogonal receiver components, the bound resolves a conjecture by Kim on a class of deterministic relay channels. When further specialized to the class of product-form relay channels with orthogonal receiver components, the bound resolves a generalized version of Cover’s relay channel problem, recovers the recent upper bound for the Gaussian case by Wu et al., and improves upon the recent bounds for the binary symmetric case by Wu et al. and Barnes et al., which were obtained using non-traditional geometric proof techniques. For the special class of a relay channel with orthogonal receiver components, we develop another upper bound on the capacity which utilizes an auxiliary receiver and show that it is strictly tighter than the bound by Tandon and Ulukus. Finally, we show through the Gaussian relay channel with i.i.d. relay output sequence that the bound with the auxiliary receiver can be strictly tighter than our main bound.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • The Feedback Capacity of Noisy Output Is the STate (NOST) Channels

    • Free pre-print version: Loading...

      Authors: Eli Shemuel;Oron Sabag;Haim H. Permuter;
      Pages: 5044 - 5059
      Abstract: We consider finite-state channels (FSCs) where the channel state is stochastically dependent on the previous channel output. We refer to these as Noisy Output is the STate (NOST) channels. We derive the feedback capacity of NOST channels in two scenarios: with and without causal state information (CSI) available at the encoder. If CSI is unavailable, the feedback capacity is $C_{text {FB}}= max _{P(x y')} I(X;Y Y')$ , while if it is available at the encoder, the feedback capacity is $C_{text {FB-CSI}}= max _{P(u y'),x(u,s')} I(U;Y Y')$ , where $U$ is an auxiliary RV with finite cardinality. In both formulas, the output process is a Markov process with stationary distribution. The derived formulas generalize special known instances from the literature, such as where the state is i.i.d. and where it is a deterministic function of the output. $C_{text {FB}}$ and $C_{text {FB-CSI}}$ are also shown to be computable via convex optimization problem formulations. Finally, we present an example of an interesting NOST channel for which CSI available at the encoder does not increase the feedback capacity.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Optimal Locally Repairable Codes: An Improved Bound and Constructions

    • Free pre-print version: Loading...

      Authors: Han Cai;Cuiling Fan;Ying Miao;Moshe Schwartz;Xiaohu Tang;
      Pages: 5060 - 5074
      Abstract: We study the Singleton-type bound that provides an upper limit on the minimum distance of locally repairable codes. We present an improved bound by carefully analyzing the combinatorial structure of the repair sets. Thus, we show the previous bound is unachievable for certain parameters. We then also provide explicit constructions of optimal codes which show that for certain parameters the new bound is sharp. Additionally, as a byproduct, some previously known codes are shown to attain the new bound and are thus proved to be optimal.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Generic Decoding in the Sum-Rank Metric

    • Free pre-print version: Loading...

      Authors: Sven Puchinger;Julian Renner;Johan Rosenkilde;
      Pages: 5075 - 5097
      Abstract: We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders. Furthermore, we give a formal hardness reduction, providing evidence that generic sum-rank decoding is computationally hard. As a by-product of the above, we solve some fundamental coding problems in the sum-rank metric: we give an algorithm to compute the exact size of a sphere of a given sum-rank radius, and also give an upper bound as a closed formula; and we study erasure decoding with respect to two different notions of support.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Multiple-Layer Integrated Interleaved Codes: A Class of Hierarchical
           Locally Recoverable Codes

    • Free pre-print version: Loading...

      Authors: Mario Blaum;
      Pages: 5098 - 5111
      Abstract: The traditional definition of Integrated Interleaved (II) codes generally assumes that the component nested codes are either Reed-Solomon (RS) or shortened Reed-Solomon codes. By taking general classes of codes, we present a recursive construction of Extended Integrated Interleaved (EII) codes into multiple layers, a problem that brought attention in literature for II codes. The multiple layer approach allows for a hierarchical scheme where each layer of the code provides for a different locality. In particular, we present the erasure-correcting capability of the new codes and we show that they are ideally suited as Locally Recoverable codes (LRC) due to their hierarchical locality and the small finite field required by the construction. Properties of the multiple layer EII codes, like their minimum distance and dimension, as well as their erasure decoding algorithms, parity-check matrices and performance analysis, are provided and illustrated with examples. Finally, we will observe that the parity-check matrices of high layer EII codes have low density.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Sparse and Balanced MDS Codes Over Small Fields

    • Free pre-print version: Loading...

      Authors: Tingting Chen;Xiande Zhang;
      Pages: 5112 - 5125
      Abstract: Maximum Distance Separable (MDS) codes with a sparse and balanced generator matrix are appealing in distributed storage systems for balancing and minimizing the computational load. Such codes have been constructed via Reed-Solomon codes over large fields. In this paper, we focus on small fields. We prove that there exists an $[n,k]_{q}$ MDS code that has a sparse and balanced generator matrix for any $qgeq n-1$ provided that $nleq 2k$ , by designing several algorithms with complexity running in polynomial time in $k$ and $n$ . For the case $n>2k$ , we give some constructions for $q=n=p^{s}$ and $k=p^{e}m$ based on sumsets, when $eleq s-2$ and $mleq p-1$ , or $e=s-1$ and $m < frac {p}{2}$ .
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Coordinate-Ordering-Free Upper Bounds for Linear Insertion-Deletion Codes

    • Free pre-print version: Loading...

      Authors: Hao Chen;
      Pages: 5126 - 5132
      Abstract: In this paper we prove several coordinate-ordering-free upper bounds on the insdel distances of linear codes. Our bounds are stronger than some previous known bounds. We apply these upper bounds to AGFC codes from some cyclic codes and one algebraic-geometric code with any rearrangement of coordinate positions. A strong upper bound on the insdel distances of Reed-Muller codes with the special coordinate ordering is also given.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • A Galois Connection Approach to Wei-Type Duality Theorems

    • Free pre-print version: Loading...

      Authors: Yang Xu;Haibin Kan;Guangyue Han;
      Pages: 5133 - 5144
      Abstract: In 1991, Wei proved a duality theorem that established an interesting connection between the generalized Hamming weights of a linear code and those of its dual code. Wei’s duality theorem has since been extensively studied from different perspectives and extended to other settings. In this paper, we re-examine Wei’s duality theorem and its various extensions, henceforth referred to as Wei-type duality theorems, from a new Galois connection perspective. Our approach is based on the observation that the generalized Hamming weights and the dimension/length profiles of a linear code form a Galois connection. The central result of this paper is a general Wei-type duality theorem for two Galois connections between finite subsets of $mathbb {Z}$ , from which all the known Wei-type duality theorems can be recovered. As corollaries of our central result, we prove new Wei-type duality theorems for $w$ -demi-matroids defined over finite sets and $w$ -demi-polymatroids defined over modules with a composition series, which further allows us to unify and generalize all the known Wei-type duality theorems established for codes endowed with various metrics.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Enumeration of Extended Irreducible Binary Goppa Codes

    • Free pre-print version: Loading...

      Authors: Bocong Chen;Guanghui Zhang;
      Pages: 5145 - 5153
      Abstract: The family of Goppa codes is one of the most interesting subclasses of linear codes. As the McEliece cryptosystem often chooses a random Goppa code as its key, knowledge of the number of inequivalent Goppa codes for fixed parameters may facilitate in the evaluation of the security of such a cryptosystem. In this paper we present a new approach to give an upper bound on the number of inequivalent extended irreducible binary Goppa codes. To be more specific, let $n>3$ be an odd prime number and $q=2^{n}$ ; let $rgeq 3$ be a positive integer satisfying $gcd (r,n)=1$ and $gcd big (r,q(q^{2}-1)big)=1$ . We obtain an upper bound for the number of inequivalent extended irreducible binary Goppa codes of length $q+1$ and degree $r$ .
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Q-Ary Non-Overlapping Codes: A Generating Function
           Approach

    • Free pre-print version: Loading...

      Authors: Geyang Wang;Qi Wang;
      Pages: 5154 - 5164
      Abstract: Non-overlapping codes are a set of codewords in $bigcup _{n ge 2} mathbb {Z}_{q}^{n}$ , where $mathbb {Z}_{q} = {0,1, {dots },q-1}$ , such that the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$ -ary ones for $q> 2$ , and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the latter construction is the first attempt to generate $q$ -ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$ -ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the superior limit of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwor-s. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Nonlinear Repair of Reed-Solomon Codes

    • Free pre-print version: Loading...

      Authors: Roni Con;Itzhak Tamo;
      Pages: 5165 - 5177
      Abstract: The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised by Guruswami and Wootters, 2017, on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Lastly, we show that the cut-set bound for RS codes is not tight over prime fields by proving a tighter bound, using additive combinatorics ideas.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Convolutional Codes With a Maximum Distance Profile Based on Skew
           Polynomials

    • Free pre-print version: Loading...

      Authors: Zitan Chen;
      Pages: 5178 - 5184
      Abstract: We construct a family of $(n,k)$ convolutional codes with degree $delta in {k,n-k}$ that have a maximum distance profile. The field size required for our construction is $Theta (n^{2delta })$ , which improves upon the known constructions of convolutional codes with a maximum distance profile. Our construction is based on the theory of skew polynomials.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Precoding and Scheduling for AoI Minimization in MIMO Broadcast Channels

    • Free pre-print version: Loading...

      Authors: Songtao Feng;Jing Yang;
      Pages: 5185 - 5202
      Abstract: In this paper, we consider a status updating system where updates are generated at a constant rate at $K$ sources and sent to the corresponding recipients through a noise-free broadcast channel. We assume that perfect channel state information (CSI) is available at the transmitter before each transmission, and the transmitter is able to utilize the CSI to precode the updates. Our object is to design optimal precoding schemes to minimize the summed average age of information (AoI) at the recipients. Under various assumptions on the size of each update $B$ , the number of transmit antennas $M$ , and the number of receive antennas $N$ at each user, this paper identifies the corresponding age-optimal precoding and transmission scheduling strategies. Specifically, for the case when $N=1$ , a round-robin based updating scheme is shown to be optimal. For the two-user systems with $N>B$ or $Mnotin [N:2N]$ , framed updating schemes are proven to be optimal. For other cases in the two-user systems, a framed alternating updating scheme is proven to be 2-optimal.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • A Framework for Characterizing the Value of Information in Hidden Markov
           Models

    • Free pre-print version: Loading...

      Authors: Zijing Wang;Mihai-Alin Badiu;Justin P. Coon;
      Pages: 5203 - 5216
      Abstract: In this paper, a general framework is formalised to characterise the value of information (VoI) in hidden Markov models. Specifically, the VoI is defined as the mutual information between the current, unobserved status at the source and a sequence of observed measurements at the receiver, which can be interpreted as the reduction in the uncertainty of the current status given that we have noisy past observations of a hidden Markov process. We explore the VoI in the context of the noisy Ornstein-Uhlenbeck process and derive its closed-form expressions. Moreover, we investigate the effect of different sampling policies on VoI, deriving simplified expressions in different noise regimes and analysing statistical properties of the VoI in the worst case. We also study the optimal sampling policy to maximise the average information value under the sampling rate constraint. In simulations, the validity of theoretical results is verified, and the performance of VoI in Markov and hidden Markov models is also analysed. Numerical results further illustrate that the proposed VoI framework can support timely transmission in status update systems, and it can also capture the correlation properties of the underlying random process and the noise in the transmission environment.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Quantum Differentially Private Sparse Regression Learning

    • Free pre-print version: Loading...

      Authors: Yuxuan Du;Min-Hsiu Hsieh;Tongliang Liu;Shan You;Dacheng Tao;
      Pages: 5217 - 5233
      Abstract: The eligibility of various advanced quantum algorithms will be questioned if they can not guarantee privacy. To fill this knowledge gap, here we devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Concretely, given $N~d$ -dimensional data points with $Nll d$ , we first prove that the optimal classical and quantum non-private Lasso requires $Omega (N+d)$ and $Omega (sqrt {N}+sqrt {d})$ runtime, respectively. We next prove that the runtime cost of QDP Lasso is dimension independent, i.e., $O(N^{5/2})$ , which implies that the QDP Lasso can be faster than both the optimal classical and quantum non-private Lasso. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $tilde {O}(N^{-2/3})$ with privacy guarantees and discuss the chance to realize it on near-term quantum chips with advantages.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Linear Programming Bounds for Approximate Quantum Error Correction Over
           Arbitrary Quantum Channels

    • Free pre-print version: Loading...

      Authors: Yingkai Ouyang;Ching-Yi Lai;
      Pages: 5234 - 5247
      Abstract: While quantum weight enumerators establish some of the best upper bounds on the minimum distance of quantum error-correcting codes, these bounds are not optimized to quantify the performance of quantum codes under the effect of arbitrary quantum channels that describe bespoke noise models. Herein, for any Kraus decomposition of any given quantum channel, we introduce corresponding quantum weight enumerators that naturally generalize the Shor-Laflamme quantum weight enumerators. We establish an indirect linear relationship between these generalized quantum weight enumerators by introducing an auxiliary exact weight enumerator that completely quantifies the quantum code’s projector, and is independent of the underlying noise process. By additionally working within the framework of approximate quantum error correction, we establish a general framework for constructing a linear program that is infeasible whenever approximate quantum error correcting codes with corresponding parameters do not exist. Our linear programming framework allows us to establish the non-existence of certain quantum codes that approximately correct amplitude damping errors, and obtain non-trivial upper bounds on the maximum dimension of a broad family of permutation-invariant quantum codes.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed
           Bandits

    • Free pre-print version: Loading...

      Authors: Anmol Kagrecha;Jayakrishnan Nair;Krishna Jagannathan;
      Pages: 5248 - 5267
      Abstract: Traditional multi-armed bandit (MAB) formulations usually make certain assumptions about the underlying arms’ distributions, such as bounds on the support or their tail behaviour. Moreover, such parametric information is usually ‘baked’ into the algorithms. In this paper, we show that specialized algorithms that exploit such parametric information are prone to inconsistent learning performance when the parameter is misspecified. Our key contributions are twofold: (i) We establish fundamental performance limits of statistically robust MAB algorithms under the fixed-budget pure exploration setting, and (ii) We propose two classes of algorithms that are asymptotically near-optimal. Additionally, we consider a risk-aware criterion for best arm identification, where the objective associated with each arm is a linear combination of the mean and the conditional value at risk (CVaR). Throughout, we make a very mild ‘bounded moment’ assumption, which lets us work with both light-tailed and heavy-tailed distributions within a unified framework.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • The Price of Competition: Effect Size Heterogeneity Matters in High
           Dimensions

    • Free pre-print version: Loading...

      Authors: Hua Wang;Yachong Yang;Weijie J. Su;
      Pages: 5268 - 5294
      Abstract: In high-dimensional sparse regression, would increasing the signal-to-noise ratio while fixing the sparsity level always lead to better model selection' For high-dimensional sparse regression problems, surprisingly, in this paper we answer this question in the negative in the regime of linear sparsity for the Lasso method, relying on a new concept we term effect size heterogeneity. Roughly speaking, a regression coefficient vector has high effect size heterogeneity if its nonzero entries have significantly different magnitudes. From the viewpoint of this new measure, we prove that the false and true positive rates achieve the optimal trade-off uniformly along the Lasso path when this measure is maximal in a certain sense, and the worst trade-off is achieved when it is minimal in the sense that all nonzero effect sizes are roughly equal. Moreover, we demonstrate that the first false selection occurs much earlier when effect size heterogeneity is minimal than when it is maximal. The underlying cause of these two phenomena is, metaphorically speaking, the “competition” among variables with effect sizes of the same magnitude in entering the model. Taken together, our findings suggest that effect size heterogeneity shall serve as an important complementary measure to the sparsity of regression coefficients in the analysis of high-dimensional regression problems. Our proofs use techniques from approximate message passing theory as well as a novel technique for estimating the rank of the first false variable.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • On Loss Functions and Regret Bounds for Multi-Category Classification

    • Free pre-print version: Loading...

      Authors: Zhiqiang Tan;Xinwei Zhang;
      Pages: 5295 - 5313
      Abstract: We develop new approaches in multi-class settings for constructing loss functions and establishing corresponding regret bounds with respect to the zero-one or cost-weighted classification loss. We provide new general representations of losses by deriving inverse mappings from a concave generalized entropy to a loss through a convex dissimilarity function related to the multi-distribution $f$ -divergence. This approach is then applied to study both hinge-like losses and proper scoring rules. In the first case, we derive new hinge-like convex losses, which are tighter extensions outside the probability simplex than related hinge-like losses and geometrically simpler with fewer non-differentiable edges. We also establish a classification regret bound in general for all losses with the same generalized entropy as the zero-one loss, thereby substantially extending and improving existing results. In the second case, we identify new sets of multi-class proper scoring rules through different types of dissimilarity functions and reveal interesting relationships between various composite losses currently in use. We also establish new classification regret bounds in general for multi-class proper scoring rules and, as applications, provide simple meaningful regret bounds for two specific sets of proper scoring rules. These results generalize, for the first time, previous two-class regret bounds to multi-class settings.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Minimax Off-Policy Evaluation for Multi-Armed Bandits

    • Free pre-print version: Loading...

      Authors: Cong Ma;Banghua Zhu;Jiantao Jiao;Martin J. Wainwright;
      Pages: 5314 - 5339
      Abstract: We study the problem of off-policy evaluation in the multi-armed bandit model with bounded rewards, and develop minimax rate-optimal procedures under three settings. First, when the behavior policy is known, we show that the Switch estimator, a method that alternates between the plug-in and importance sampling estimators, is minimax rate-optimal for all sample sizes. Second, when the behavior policy is unknown, we analyze performance in terms of the competitive ratio, thereby revealing a fundamental gap between the settings of known and unknown behavior policies. When the behavior policy is unknown, any estimator must have mean-squared error larger—relative to the oracle estimator equipped with the knowledge of the behavior policy— by a multiplicative factor proportional to the support size of the target policy. Moreover, we demonstrate that the plug-in approach achieves this worst-case competitive ratio up to a logarithmic factor. Third, we initiate the study of the partial knowledge setting in which it is assumed that the minimum probability taken by the behavior policy is known. We show that the plug-in estimator is optimal for relatively large values of the minimum probability, but is sub-optimal when the minimum probability is low. In order to remedy this gap, we propose a new estimator based on approximation by Chebyshev polynomials that provably achieves the optimal estimation error. Numerical experiments on both simulated and real data corroborate our theoretical findings.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Convex Formulation of Overparameterized Deep Neural Networks

    • Free pre-print version: Loading...

      Authors: Cong Fang;Yihong Gu;Weizhong Zhang;Tong Zhang;
      Pages: 5340 - 5352
      Abstract: The analysis of over-parameterized neural networks has drawn significant attention in recent years. It was shown that such systems behave like convex systems under various restricted settings, such as for two-layer neural networks, and when learning is only restricted locally in the so-called neural tangent kernel space around specialized initializations. However, there is a lack of powerful theoretical techniques that can analyze fully trained deep neural networks under general conditions. This paper considers this fundamental problem by investigating such overparameterized deep neural networks when fully trained. Specifically, we characterize a deep neural network by its features’ distributions and propose a metric to intuitively measure the usefulness of feature representations. Under certain regularizers that bounds the metric, we show deep neural networks can be reformulated as a convex optimization and the system can guarantee effective feature representations in terms of the metric. Our new analysis is more consistent with empirical observations that deep neural networks are capable of learning efficient feature representations. Empirical studies confirm that predictions of our theory are consistent with results observed in practice.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Tsallis and Rényi Deformations Linked via a New λ-Duality

    • Free pre-print version: Loading...

      Authors: Ting-Kam Leonard Wong;Jun Zhang;
      Pages: 5353 - 5373
      Abstract: Tsallis and Rényi entropies, which are monotone transformations of each other, are deformations of the celebrated Shannon entropy. Maximization of these deformed entropies, under suitable constraints, leads to the $q$ -exponential family which has applications in non-extensive statistical physics, information theory and statistics. In previous information-geometric studies, the $q$ -exponential family was analyzed using classical convex duality and Bregman divergence. In this paper, we show that a generalized $lambda $ -duality, where $lambda = 1 - q$ is to be interpreted as the constant information-geometric curvature, leads to a generalized exponential family which is essentially equivalent to the $q$ -exponential family and has deep connections with Rényi entropy and optimal transport. Using this generalized convex duality and its associated logarithmic divergence, we show that our $lambda $ -exponential family satisfies properties that parallel and generalize those of the exponential family. Under our framework, the Rényi entropy and divergence arise naturally, and we give a new proof of the Tsallis/Rényi entropy maximizing property of the $q$ -exponential family. We also introduce a $lambda $ -mixture family which may be regarded as the dual of the $lambda $ -exponential family, and connect it with other mixture-type families. Finally, we discuss a duality between the $lambda $ -exponential family and the $lambda $ -logarithmic divergence, and study its statistical consequences.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • SDP Achieves Exact Minimax Optimality in Phase Synchronization

    • Free pre-print version: Loading...

      Authors: Chao Gao;Anderson Y. Zhang;
      Pages: 5374 - 5390
      Abstract: We study the phase synchronization problem with noisy measurements $Y=z^{*}z^{* { mathrm {scriptscriptstyle H} }}+sigma Win mathbb {C}^{ntimes n}$ , where $z^{*}$ is an $n$ -dimensional complex unit-modulus vector and $W$ is a complex-valued Gaussian random matrix. It is assumed that each entry $Y_{jk}$ is observed with probability $p$ . We prove that an SDP relaxation of the MLE achieves the error bound $(1+o(1))frac {sigma ^{2}}{2np}$ under a normalized squared $ell _{2}$ loss. This result matches the minimax lower bound of the problem, and even the leading constant is sharp. The analysis of the SDP is based on an equivalent non-convex programming whose solution can be characterized as a fixed point of the generalized power iteration lifted to a higher dimensional space. This viewpoint unifies the proofs of the statistical optimality of three different methods: MLE, SDP, and generalized power method. The technique is also applied to the analysis of the SDP for $mathbb {Z}_{2}$ synchronization, and we achieve the minimax optimal error $exp left ({-(1-o(1))frac {np}{2sigma ^{2}}}right)$ with a sharp constant in the exponent.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Settling the Sharp Reconstruction Thresholds of Random Graph Matching

    • Free pre-print version: Loading...

      Authors: Yihong Wu;Jiaming Xu;Sophie H. Yu;
      Pages: 5391 - 5417
      Abstract: This paper studies the problem of recovering the hidden vertex correspondence between two edge-correlated random graphs. We focus on the Gaussian model where the two graphs are complete graphs with correlated Gaussian weights and the Erdős-Rényi model where the two graphs are subsampled from a common parent Erdős-Rényi graph ${mathcal {G}}(n,p)$ . For dense Erdős-Rényi graphs with $p=n^{-o(1)}$ , we prove that there exists a sharp threshold, above which one can correctly match all but a vanishing fraction of vertices and below which correctly matching any positive fraction is impossible, a phenomenon known as the “all-or-nothing” phase transition. Even more strikingly, in the Gaussian setting, above the threshold all vertices can be exactly matched with high probability. In contrast, for sparse Erdős-Rényi graphs with $p=n^{-Theta (1)}$ , we show that the all-or-nothing phenomenon no longer holds and we determine the thresholds up to a constant factor. Along the way, we also derive the sharp threshold for exact recovery, sharpening the existing results in Erdős-Rényi graphs. The proof of the negative results builds upon a tight characterization of the mutual information based on the truncated second-moment computation and an “area theorem” that relates the mutual information to the integral of the reconstruction error. The positive results follows from a tight analysis of the maximum likelihood estimator that takes into account the cycle structure of the induced permutation on the edges.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • X-Secure T-Private Federated Submodel Learning With Elastic Dropout
           Resilience

    • Free pre-print version: Loading...

      Authors: Zhuqing Jia;Syed Ali Jafar;
      Pages: 5418 - 5439
      Abstract: Motivated by recent interest in federated submodel learning, this work explores the fundamental problem of privately reading from and writing to a database comprised of $K$ files (submodels) that are stored across $N$ distributed servers according to an $X$ -secure threshold secret sharing scheme. One after another, various users wish to retrieve their desired file, locally process the information and then update the file in the distributed database while keeping the identity of their desired file private from any set of up to $T$ colluding servers. The availability of servers changes over time, so elastic dropout resilience is required. The main contribution of this work is an adaptive scheme, called ACSA-RW, that takes advantage of all currently available servers to reduce its communication costs, fully updates the database after each write operation even though the database is only partially accessible due to server dropouts, and ensures a memoryless operation of the network in the sense that the storage structure is preserved and future users may remain oblivious of the past history of server dropouts. The ACSA-RW construction builds upon cross-subspace alignment (CSA) codes that were originally introduced for $X$ -secure $T$ -private information retrieval and have been shown to be natural solutions for secure distributed batch matrix multiplication problems. ACSA-RW achieves the desired private read and write functionality with elastic dropout resilience, matches the best results for private-read from PIR literature, improves signifi-antly upon available baselines for private-write, reveals a striking symmetry between upload and download costs, and exploits storage redundancy to accommodate arbitrary read and write dropout servers up to certain threshold values. It also answers in the affirmative an open question by Kairouz et al. for the case of partially colluding servers (i.e., tolerating collusion up to a threshold) by exploiting synergistic gains from the joint design of private read and write operations.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Keyless Covert Communication via Channel State Information

    • Free pre-print version: Loading...

      Authors: Hassan Zivarifard;Matthieu R. Bloch;Aria Nosratinia;
      Pages: 5440 - 5474
      Abstract: We consider the problem of covert communication over a state-dependent channel when the Channel State Information (CSI) is available either non-causally, causally, or strictly causally, either at the transmitter alone, or at both transmitter and receiver. Covert communication with respect to an adversary, called “warden,” is one in which, despite communication over the channel, the warden’s observation remains indistinguishable from an output induced by innocent channel-input symbols. Covert communication involves fooling an adversary in part by a proliferation of codebooks; for reliable decoding at the legitimate receiver, the codebook uncertainty is typically removed via a shared secret key that is unavailable to the warden. In contrast to previous work, we do not assume the availability of a large shared key at the transmitter and legitimate receiver. Instead, we only require a secret key with negligible rate to bootstrap the communication and our scheme extracts shared randomness from the CSI in a manner that keeps it secret from the warden, despite the influence of the CSI on the warden’s output. When CSI is available at the transmitter and receiver, we derive the covert capacity region. When CSI is only available at the transmitter, we derive inner and outer bounds on the covert capacity. We also provide examples for which the covert capacity is positive with knowledge of CSI but is zero without it.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Privacy Amplification With Tamperable Memory via Non-Malleable Two-Source
           Extractors

    • Free pre-print version: Loading...

      Authors: Divesh Aggarwal;Maciej Obremski;João Ribeiro;Mark Simkin;Luisa Siniscalchi;
      Pages: 5475 - 5495
      Abstract: We extend the classical problem of privacy amplification to a setting where the active adversary, Eve, is also allowed to fully corrupt the internal memory (which includes the shared randomness, and local randomness tape) of one of the honest parties, Alice and Bob, before the execution of the protocol. We require that either one of Alice or Bob detects tampering, or they agree on a shared key that is indistinguishable from the uniform distribution to Eve. We obtain the following results: 1) we give a privacy amplification protocol via low-error non-malleable two-source extractors with one source having low min-entropy. In particular, this implies the existence of such (non-efficient) protocols; 2) we show that even slight improvements to the state-of-the-art explicit non-malleable two-source extractors would lead to explicit low-error, low min-entropy two-source extractors, thereby resolving a long-standing open question. This suggests that obtaining (information-theoretically secure) explicit non-malleable two-source extractors for (1) might be hard; 3) we present explicit constructions of low-error, low min-entropy non-malleable two-source extractors in the CRS model of (Garg, Kalai, Khurana, Eurocrypt 2020), assuming either the quasi-polynomial hardness of DDH or the existence of nearly-optimal collision-resistant hash functions; 4) we instantiate our privacy amplification protocol with the above mentioned non-malleable two-source extractors in the CRS model, leading to explicit, computationally-secure protocols. This is not immediate from (1) because in the computational setting we need to make sure that, in particular, all randomness sources remain samplable throughout the proof. This requires upgrading the assumption of quasi-polynomial hardness of DDH to sub-exponential hardness of DDH.We emphasize that each of the first three results can be read independently.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Storage-Computation-Communication Tradeoff in Distributed Computing:
           Fundamental Limits and Complexity

    • Free pre-print version: Loading...

      Authors: Qifa Yan;Sheng Yang;Michèle Wigger;
      Pages: 5496 - 5512
      Abstract: Distributed computing has become one of the most important frameworks in dealing with large computation tasks. In this paper, we propose a systematic construction of coded computing schemes for MapReduce-type distributed systems. The construction builds upon placement delivery arrays (PDA), originally proposed by Yan et al. for coded caching schemes. The main contributions of our work are three-fold. First, we identify a class of PDAs, called Comp-PDAs, and show how to obtain a coded computing scheme from any Comp-PDA. We also characterize the normalized number of stored files (storage load), computed intermediate values (computation load), and communicated bits (communication load), of the obtained schemes in terms of the Comp-PDA parameters. Then, we show that the performance achieved by Comp-PDAs describing Maddah-Ali and Niesen’s coded caching schemes matches a new information-theoretic converse, thus establishing the fundamental region of all achievable performance triples. In particular, we characterize all the Comp-PDAs achieving the pareto-optimal storage, computation, and communication (SCC) loads of the fundamental region. Finally, we investigate the file complexity of the proposed schemes, i.e., the smallest number of files required for implementation. In particular, we describe Comp-PDAs that achieve pareto-optimal SCC triples with significantly lower file complexity than the originally proposed Comp-PDAs.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Disordered Complex Networks: Energy Optimal Lattices and Persistent
           Homology

    • Free pre-print version: Loading...

      Authors: Subhroshekhar Ghosh;Naoto Miyoshi;Tomoyuki Shirai;
      Pages: 5513 - 5534
      Abstract: Disordered complex networks are of fundamental interest in statistical physics, and they have attracted recent interest as stochastic models for information transmission over wireless networks. While mathematically tractable, a network based on the regulation Poisson point process model offers challenges vis-a-vis network efficiency. Strongly correlated alternatives, such as networks based on random matrix spectra (the Ginibre network), on the other hand offer formidable challenges in terms of tractability and robustness issues. In this work, we demonstrate that network models based on random perturbations of Euclidean lattices interpolate between Poisson and rigidly structured networks, and allow us to achieve the best of both worlds: significantly improve upon the Poisson model in terms of network efficacy measured by the Signal to Interference plus Noise Ratio (abbrv. SINR) and the related concept of coverage probabilities, at the same time retaining a considerable measure of mathematical and computational simplicity and robustness to erasure and noise. We investigate the optimal choice of the base lattice in this model, connecting it to the celebrated problem optimality of Euclidean lattices with respect to the Epstein Zeta function, which is in turn related to notions of lattice energy. This leads us to the choice of the triangular lattice in 2D and face centered cubic lattice in 3D, whose Gaussian perturbations we consider. We provide theoretical analysis and empirical investigations to demonstrate that the coverage probability decreases with increasing strength of perturbation, eventually converging to that of the Poisson network. In the regime of low disorder, our studies suggest an approximate statistical behaviour of the coverage function near a base station as a log-normal distribution with parameters depending on the Epstein Zeta function of the lattice, and related approximate dependen-ies for a power-law constant that governs the network coverage probability at large thresholds. In 2D, we determine the disorder strength at which the perturbed triangular lattice (abbrv. PTL) and the Ginibre networks are the closest measured by comparing their network topologies via a comparison of their Persistence Diagrams in the total variation as well as the symmetrized nearest neighbour distances. We demonstrate that, at this very same disorder, the PTL and the Ginibre networks exhibit very similar coverage probability distributions, with the PTL performing at least as well as the Ginibre. Thus, the PTL network at this disorder strength can be taken to be an effective substitute for the Ginibre network model, while at the same time offering the advantages of greater tractability both from theoretical and empirical perspectives.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • The Differential Spectrum of the Power Mapping x pn −3

    • Free pre-print version: Loading...

      Authors: Haode Yan;Yongbo Xia;Chunlei Li;Tor Helleseth;Maosheng Xiong;Jinquan Luo;
      Pages: 5535 - 5547
      Abstract: Let $n$ be a positive integer and $p$ a prime. The power mapping $x^{p^{n}-3}$ over ${mathbb {F}}_{p^{n}}$ has desirable differential properties, and its differential spectra for $p=2,,3$ have been determined. In this paper, for any odd prime $p$ , by investigating certain quadratic character sums and some equations over ${mathbb {F}}_{p^{n}}$ , we determine the differential spectrum of $x^{p^{n}-3}$ with a unified approach. The obtained result shows that for any given odd prime $p$ , the differential spectrum can be expressed explicitly in terms of $n$ . Compared with previous results, a special elliptic curve over ${mathbb {F}}_{p}$ plays an important role in our computation for the general case $p ge 5$ .
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Some Upper Bounds and Exact Values on Linear Complexities Over F M of
           Sidelnikov Sequences for M = 2 and 3

    • Free pre-print version: Loading...

      Authors: Min Zeng;Yuan Luo;Guo-Sheng Hu;Hong-Yeop Song;
      Pages: 5548 - 5560
      Abstract: Sidelnikov sequences, a kind of cyclotomic sequences with many desired properties such as low correlation and variable alphabet sizes, can be employed to construct a polyphase sequence family that has many applications in high-speed data communications. Recently, cyclotomic numbers have been used to investigate the linear complexity of Sidelnikov sequences, mainly about binary ones, although the limitation on the orders of the available cyclotomic numbers makes it difficult. This paper continues to study the linear complexity over $mathbb {F}_{M}$ of $M$ -ary Sidelnikov sequence of period $q-1$ using Hasse derivative, which implies $q=p^{m}$ , $mgeq 1$ and $M (q-1)$ . The $t$ th Hasse derivative formulas are presented in terms of cyclotomic numbers, and some upper bounds on the linear complexity for $M=2$ and 3 are obtained only with some additional restrictions on $q$ . Furthermore, concrete illustrations for several families of these sequences, such as $qequiv 1pmod {2}$ and $qequiv 1pmod {3}$ , show these upper bounds are tight and reachable; especially for $q=2times 3^{lambda }+1 (1leq lambda leq 20)$ , the exact linear complexities over $mathbb {F}_{3}$ of the ternary Sidelnikov sequences are determined; and it turns out that all the linear complexities of the sequences considered are very close to their periods.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • On Non-Detectability of Non-Computability and the Degree of
           Non-Computability of Solutions of Circuit and Wave Equations on Digital
           Computers

    • Free pre-print version: Loading...

      Authors: Holger Boche;Volker Pohl;
      Pages: 5561 - 5578
      Abstract: It is known that there exist mathematical problems of practical relevance which cannot be computed on a Turing machine. An important example is the calculation of the first derivative of continuously differentiable functions. This paper precisely classifies the non-computability of the first derivative, and of the maximum-norm of the first derivative in the Zheng-Weihrauch hierarchy. Based on this classification, the paper investigates whether it is possible that a Turing machine detects this non-computability of the first derivative by observing the data of the problem, and whether it is possible to detect upper bounds for the peak value of the first derivative of continuously differentiable functions. So from a practical point of view, the question is whether it is possible to implement an exit-flag functionality for observing non-computability of the first derivative. This paper even studies two different types of exit-flag functionality. A strong one, where the Turing machine always has to stop, and a weak one, where the Turing machine stops if and only if the input lies within the corresponding set of interest. It will be shown that non-computability of the first derivative is not detectable by a Turing machine for two concrete examples, namely for the problem of computing the input–output behavior of simple analog circuits and for solutions of the three-dimensional wave equation. In addition, it is shown that it is even impossible to detect an upper bound for the maximum norm of the first derivative. In particular, it is shown that all three problems are not even semidecidable. Finally, we briefly discuss implications of these results for analog and quantum computing.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
  • Macroscopic Analysis of Vector Approximate Message Passing in a
           Model-Mismatched Setting

    • Free pre-print version: Loading...

      Authors: Takashi Takahashi;Yoshiyuki Kabashima;
      Pages: 5579 - 5600
      Abstract: In this study, macroscopic properties of the vector approximate message passing (VAMP) algorithm for inference of generalized linear models are investigated using a non-rigorous heuristic method of statistical mechanics when the true posterior cannot be used and the measurement matrix is a sample from rotation-invariant random matrix ensembles. The focus is on the correspondence between the non-rigorous replica analysis of statistical mechanics and the performance assessment of VAMP in the model-mismatched setting. The correspondence of this kind is well-known when the measurement matrix has independent and identically distributed entries. However, when the measurement matrix follows a general rotation-invariant matrix ensemble, the correspondence has been validated only under limited cases, such as the Bayes optimal inference or the convex empirical risk minimization. The result presented in this paper is to extend the scope of such correspondence. Herein, we heuristically derive the explicit formula of state-evolution equations, which macroscopically describe VAMP dynamics for the current model-mismatched case, and show that their fixed point is generally consistent with the replica symmetric solution obtained by the replica method of statistical mechanics. We also show that the fixed point of VAMP can exhibit a microscopic instability, which indicates that message variables continue to move by VAMP while their macroscopically summarized quantities converge to fixed values. The critical condition the for microscopic instability agrees with that for breaking the replica symmetry that is derived within the non-rigorous replica analysis. The results of the numerical experiments cross-check our findings.
      PubDate: Aug. 2022
      Issue No: Vol. 68, No. 8 (2022)
       
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
 


Your IP address: 44.200.171.74
 
Home (Search)
API
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-