Topic overview

math.IT

3968 works7411 researchers0 institutions

Topic snapshot

What this area looks like now

3968works

7411authors

0experts visible

0communities

Next steps

Move from topic reading into action

The graph preview below keeps the nearby papers, people and communities visible in the same reading flow.

Inspect nearby papers, researchers, institutions and communities without opening a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2014arXiv

Characteristic-Dependent Linear Rank Inequalities with Applications to Network Coding

Two characteristic-dependent linear rank inequalities are given for eight variables. Specifically, the first inequality holds for all finite fields whose characteristic is not three and does not in general hold over characteristic three. The second inequality holds for all finite fields whose characteristic is three and does not in general hold over characteristics other than three. Applications of these inequalities to the computation of capacity upper bounds in network coding are demonstrated.

preprint2013arXiv

Projection Design For Statistical Compressive Sensing: A Tight Frame Based Approach

In this paper, we develop a framework to design sensing matrices for compressive sensing applications that lead to good mean squared error (MSE) performance subject to sensing cost constraints. By capitalizing on the MSE of the oracle estimator, whose performance has been shown to act as a benchmark to the performance of standard sparse recovery algorithms, we use the fact that a Parseval tight frame is the closest design - in the Frobenius norm sense - to the solution of a convex relaxation of the optimization problem that relates to the minimization of the MSE of the oracle estimator with respect to the equivalent sensing matrix, subject to sensing energy constraints. Based on this result, we then propose two sensing matrix designs that exhibit two key properties: i) the designs are closed form rather than iterative; ii) the designs exhibit superior performance in relation to other designs in the literature, which is revealed by our numerical investigation in various scenarios with different sparse recovery algorithms including basis pursuit de-noise (BPDN), the Dantzig selector and orthogonal matching pursuit (OMP).

preprint2014arXiv

One condition for solution uniqueness and robustness of both l1-synthesis and l1-analysis minimizations

The $\ell_1$-synthesis model and the $\ell_1$-analysis model recover structured signals from their undersampled measurements. The solution of former is a sparse sum of dictionary atoms, and that of the latter makes sparse correlations with dictionary atoms. This paper addresses the question: when can we trust these models to recover specific signals? We answer the question with a condition that is both necessary and sufficient to guarantee the recovery to be unique and exact and, in presence of measurement noise, to be robust. The condition is one--for--all in the sense that it applies to both of the $\ell_1$-synthesis and $\ell_1$-analysis models, to both of their constrained and unconstrained formulations, and to both the exact recovery and robust recovery cases. Furthermore, a convex infinity--norm program is introduced for numerically verifying the condition. A comprehensive comparison with related existing conditions are included.

preprint2015arXiv

Power Distribution of Device-to-Device Communications in Underlaid Cellular Networks

Device-to-device (D2D) communications have recently emerged as a novel transmission paradigm in wireless cellular networks. D2D transmissions take place concurrently with the usual cellular connections, and thus, controlling the interference brought to the macro-cellular user equipment (UE) is of vital importance. In this paper, we consider the uplink transmission of a tier of D2D users that operates as an underlay for the traditional cellular network. Using network model based on stochastic geometry, we derive the equilibrium cumulative distribution function (CDF) of the D2D transmit power. Considering interference-limited and relatively lossy environment cases, closed form equations are derived for the power CDF. Finally, a tight closed-form upper-bound for the derived power distribution is proposed, and the analytical results are validated via simulation.

preprint2016arXiv

Algebraic Properties of Polar Codes From a New Polynomial Formalism

Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attain many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a hard task and channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised fo a binary-input symmetric channel always form a decreasing set. This property turns out to have rather deep consequences on the structure of the polar code. Indeed, the permutation group of a decreasing monomial code contains a large group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from (evaluations) of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.

preprint2015arXiv

Constant Compositions in the Sphere Packing Bound for Classical-Quantum Channels

The sphere packing bound, in the form given by Shannon, Gallager and Berlekamp, was recently extended to classical-quantum channels, and it was shown that this creates a natural setting for combining probabilistic approaches with some combinatorial ones such as the Lovász theta function. In this paper, we extend the study to the case of constant composition codes. We first extend the sphere packing bound for classical-quantum channels to this case, and we then show that the obtained result is related to a variation of the Lovász theta function studied by Marton. We then propose a further extension to the case of varying channels and codewords with a constant conditional composition given a particular sequence. This extension is then applied to auxiliary channels to deduce a bound which can be interpreted as an extension of the Elias bound.

preprint2013arXiv

Achievable Rate Regions for Network Coding

Determining the achievable rate region for networks using routing, linear coding, or non-linear coding is thought to be a difficult task in general, and few are known. We describe the achievable rate regions for four interesting networks (completely for three and partially for the fourth). In addition to the known matrix-computation method for proving outer bounds for linear coding, we present a new method which yields actual characteristic-dependent linear rank inequalities from which the desired bounds follow immediately.

preprint2017arXiv

When mmWave Communications Meet Network Densification: A Scalable Interference Coordination Perspective

The millimeter-wave (mmWave) communication is envisioned to provide orders of magnitude capacity improvement. However, it is challenging to realize a sufficient link margin due to high path loss and blockages. To address this difficulty, in this paper, we explore the potential gain of ultra-densification for enhancing mmWave communications from a network-level perspective. By deploying the mmWave base stations (BSs) in an extremely dense and amorphous fashion, the access distance is reduced and the choice of serving BSs is enriched for each user, which are intuitively effective for mitigating the propagation loss and blockages. Nevertheless, co-channel interference under this model will become a performance-limiting factor. To solve this problem, we propose a large-scale channel state information (CSI) based interference coordination approach. Note that the large-scale CSI is highly location-dependent, and can be obtained with a quite low cost. Thus, the scalability of the proposed coordination framework can be guaranteed. Particularly, using only the large-scale CSI of interference links, a coordinated frequency resource block allocation problem is formulated for maximizing the minimum achievable rate of the users, which is uncovered to be a NP-hard integer programming problem. To circumvent this difficulty, a greedy scheme with polynomial-time complexity is proposed by adopting the bisection method and linear integer programming tools. Simulation results demonstrate that the proposed coordination scheme based on large-scale CSI only can still offer substantial gains over the existing methods. Moreover, although the proposed scheme is only guaranteed to converge to a local optimum, it performs well in terms of both user fairness and system efficiency.

preprint2018arXiv

Holographic Sensing

Holographic representations of data encode information in packets of equal importance that enable progressive recovery. The quality of recovered data improves as more and more packets become available. This progressive recovery of the information is independent of the order in which packets become available. Such representations are ideally suited for distributed storage and for the transmission of data packets over networks with unpredictable delays and or erasures. Several methods for holographic representations of signals and images have been proposed over the years and multiple description information theory also deals with such representations. Surprisingly, however, these methods had not been considered in the classical framework of optimal least-squares estimation theory, until very recently. We develop a least-squares approach to the design of holographic representation for stochastic data vectors, relying on the framework widely used in modeling signals and images.

preprint2016arXiv

The reversible negacyclic codes over finite fields

In this paper, by investigating the factor of the $x^n+1$, we deduce that the structure of the reversible negacyclic code over the finite field $\mathbb{F}_{q}$, where $q$ is an odd prime power. Though studying $q-$cyclotomic cosets modulo $2n$, we obtain the parameters of negacyclic BCH code of length $n=\frac{q^\ell+1}{2}$ , $n=\frac{q^m-1}{2(q-1)}$ and $n=\frac{q^{t\cdot2^τ}-1}{2(q^t+1)}$. Some optimal linear codes from negacyclic codes are given. Finally, we discuss a class of MDS LCD negacyclic codes.

preprint2018arXiv

Some new bounds on LCD codes over finite fields

In this paper, we show that LCD codes are not equivalent to linear codes over small finite fields. The enumeration of binary optimal LCD codes is obtained. We also get the exact value of LD$(n,2)$ over $\mathbb{F}_3$ and $\mathbb{F}_4$. We study the bound of LCD codes over $\mathbb{F}_q$.

preprint2018arXiv

Minimax Learning for Remote Prediction

The classical problem of supervised learning is to infer an accurate predictor of a target variable $Y$ from a measured variable $X$ by using a finite number of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, in this paper we consider a variation of this classical problem in which the prediction is performed remotely based on a rate-constrained description $M$ of $X$. Upon receiving $M$, the remote node computes an estimate $\hat Y$ of $Y$. We follow the recent minimax approach to study this learning problem and show that it corresponds to a one-shot minimax noisy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost and a general method to design a near-optimal descriptor-estimator pair, which can be viewed as a rate-constrained analog to the maximum conditional entropy principle used in the classical minimax learning problem. Our results show that a naive estimate-compress scheme for rate-constrained prediction is not in general optimal.

preprint2019arXiv

3GPP-inspired Stochastic Geometry-based Mobility Model for a Drone Cellular Network

This paper deals with the stochastic geometry-based characterization of the time-varying performance of a drone cellular network in which the initial locations of drone base stations (DBSs) are modeled as a Poisson point process (PPP) and each DBS is assumed to move on a straight line in a random direction. This drone placement and trajectory model closely emulates the one used by the third generation partnership project (3GPP) for drone-related studies. Assuming the nearest neighbor association policy for a typical user equipment (UE) on the ground, we consider two models for the mobility of the serving DBS: (i) UE independent model, and (ii) UE dependent model. Using displacement theorem from stochastic geometry, we characterize the time-varying interference field as seen by the typical UE, using which we derive the time-varying coverage probability and data rate at the typical UE. We also compare our model with more sophisticated mobility models where the DBSs may move in nonlinear trajectories and demonstrate that the coverage probability and rate estimated by our model act as lower bounds to these more general models. To the best of our knowledge, this is the first work to perform a rigorous analysis of the 3GPP-inspired drone mobility model and establish connection between this model and the more general non-linear mobility models.

preprint2018arXiv

Fast Signal Recovery from Saturated Measurements by Linear Loss and Nonconvex Penalties

Sign information is the key to overcoming the inevitable saturation error in compressive sensing systems, which causes information loss and results in bias. For sparse signal recovery from saturation, we propose to use a linear loss to improve the effectiveness from existing methods that utilize hard constraints/hinge loss for sign consistency. Due to the use of linear loss, an analytical solution in the update progress is obtained, and some nonconvex penalties are applicable, e.g., the minimax concave penalty, the $\ell_0$ norm, and the sorted $\ell_1$ norm. Theoretical analysis reveals that the estimation error can still be bounded. Generally, with linear loss and nonconvex penalties, the recovery performance is significantly improved, and the computational time is largely saved, which is verified by the numerical experiments.

preprint2018arXiv

Information theory for fields

A physical field has an infinite number of degrees of freedom since it has a field value at each location of a continuous space. Therefore, it is impossible to know a field from finite measurements alone and prior information on the field is essential for field inference. An information theory for fields is needed to join the measurement and prior information into probabilistic statements on field configurations. Such an information field theory (IFT) is built upon the language of mathematical physics, in particular on field theory and statistical mechanics. IFT permits the mathematical derivation of optimal imaging algorithms, data analysis methods, and even computer simulation schemes. The application of IFT algorithms to astronomical datasets provides high fidelity images of the Universe and facilitates the search for subtle statistical signals from the Big Bang. The concepts of IFT might even pave the road to novel computer simulations that are aware of their own uncertainties.

preprint2019arXiv

A Scalable Max-Consensus Protocol For Noisy Ultra-Dense Networks

We introduce \emph{ScalableMax}, a novel communication scheme for achieving max-consensus in a network of multiple agents which harnesses the interference in the wireless channel as well as its multicast capabilities. In a sufficiently dense network, the amount of communication resources required grows logarithmically with the number of nodes, while in state-of-the-art approaches, this growth is at least linear. ScalableMax can handle additive noise and works well in a high SNR regime. For medium and low SNR, we propose the \emph{ScalableMax-EC} scheme, which extends the ideas of ScalableMax by introducing a novel error correction scheme. It achieves lower error rates at the cost of using more channel resources. However, it preserves the logarithmic growth with the number of agents in the system.

preprint2019arXiv

Determinant Codes with Helper-Independent Repair for Single and Multiple Failures

Determinant codes are a class of exact-repair regenerating codes for distributed storage systems with parameters (n, k = d, d). These codes cover the entire trade-off between per-node storage and repair-bandwidth. In an earlier work of the authors, the repair data of the determinant code sent by a helper node to repair a failed node depends on the identity of the other helper nodes participating in the process, which is practically undesired. In this work, a new repair mechanism is proposed for determinant codes, which relaxes this dependency, while preserving all other properties of the code. Moreover, it is shown that the determinant codes are capable of repairing multiple failures, with a per-node repair-bandwidth which scales sub-linearly with the number of failures.

preprint2019arXiv

Generalized Approximate Survey Propagation for High-Dimensional Estimation

In Generalized Linear Estimation (GLE) problems, we seek to estimate a signal that is observed through a linear transform followed by a component-wise, possibly nonlinear and noisy, channel. In the Bayesian optimal setting, Generalized Approximate Message Passing (GAMP) is known to achieve optimal performance for GLE. However, its performance can significantly degrade whenever there is a mismatch between the assumed and the true generative model, a situation frequently encountered in practice. In this paper, we propose a new algorithm, named Generalized Approximate Survey Propagation (GASP), for solving GLE in the presence of prior or model mis-specifications. As a prototypical example, we consider the phase retrieval problem, where we show that GASP outperforms the corresponding GAMP, reducing the reconstruction threshold and, for certain choices of its parameters, approaching Bayesian optimal performance. Furthermore, we present a set of State Evolution equations that exactly characterize the dynamics of GASP in the high-dimensional limit.

preprint2019arXiv

Maritime Coverage Enhancement Using UAVs Coordinated with Hybrid Satellite-Terrestrial Networks

Due to its agile maneuverability, unmanned aerial vehicles (UAVs) have shown great promise for ondemand communications. In practice, UAV-aided aerial base stations are not separate. Instead, they rely on existing satellites/terrestrial systems for spectrum sharing and efficient backhaul. In this case, how to coordinate satellites, UAVs and terrestrial systems is still an open issue. In this paper, we deploy UAVs for coverage enhancement of a hybrid satellite-terrestrial maritime communication network. Under the typical composite channel model including both large-scale and small-scale fading, the UAV trajectory and in-flight transmit power are jointly optimized, subject to constraints on UAV kinematics, tolerable interference, backhaul, and the total energy of UAV for communications. Different from existing studies, only the location-dependent large-scale channel state information (CSI) is assumed available, because it is difficult to obtain the small-scale CSI before takeoff in practice, and the ship positions can be obtained via the dedicated maritime Automatic Identification System. The optimization problem is non-convex. We solve it by problem decomposition, successive convex optimization and bisection searching tools. Simulation results demonstrate that the UAV fits well with existing satellite and terrestrial systems, using the proposed optimization framework.

preprint2019arXiv

Practical Algebraic Attack on DAGS

DAGS scheme is a key encapsulation mechanism (KEM) based on quasi-dyadic alternant codes that was submitted to NIST standardization process for a quantum resistant public key algorithm. Recently an algebraic attack was devised by Barelli and Couvreur (Asiacrypt 2018) that efficiently recovers the private key. It shows that DAGS can be totally cryptanalysed by solving a system of bilinear polynomial equations. However, some sets of DAGS parameters were not broken in practice. In this paper we improve the algebraic attack by showing that the original approach was not optimal in terms of the ratio of the number of equations to the number of variables. Contrary to the common belief that reducing at any cost the number of variables in a polynomial system is always beneficial, we actually observed that, provided that the ratio is increased and up to a threshold, the solving can be heavily improved by adding variables to the polynomial system. This enables us to recover the private keys in a few seconds. Furthermore, our experimentations also show that the maximum degree reached during the computation of the Gröbner basis is an important parameter that explains the efficiency of the attack. Finally, the authors of DAGS updated the parameters to take into account the algebraic cryptanalysis of Barelli and Couvreur. In the present article, we propose a hybrid approach that performs an exhaustive search on some variables and computes a Gröbner basis on the polynomial system involving the remaining variables. We then show that the updated set of parameters corresponding to 128-bit security can be broken with 2^83 operations.

preprint2018arXiv

Skew Cyclic Codes Over $\mathbb{F}_4 R$

This paper considers a new alphabet set, which is a ring that we call $\mathbb{F}_4R$, to construct linear error-control codes. Skew cyclic codes over the ring are then investigated in details. We define a nondegenerate inner product and provide a criteria to test for self-orthogonality. Results on the algebraic structures lead us to characterize $\mathbb{F}_4R$-skew cyclic codes. Interesting connections between the image of such codes under the Gray map to linear cyclic and skew-cyclic codes over $\mathbb{F}_4$ are shown. These allow us to learn about the relative dimension and distance profile of the resulting codes. Our setup provides a natural connection to DNA codes where additional biomolecular constraints must be incorporated into the design. We present a characterization of $R$-skew cyclic codes which are reversible complement.

preprint2019arXiv

Quickly Finding the Best Linear Model in High Dimensions

We study the problem of finding the best linear model that can minimize least-squares loss given a data-set. While this problem is trivial in the low dimensional regime, it becomes more interesting in high dimensions where the population minimizer is assumed to lie on a manifold such as sparse vectors. We propose projected gradient descent (PGD) algorithm to estimate the population minimizer in the finite sample regime. We establish linear convergence rate and data dependent estimation error bounds for PGD. Our contributions include: 1) The results are established for heavier tailed sub-exponential distributions besides sub-gaussian. 2) We directly analyze the empirical risk minimization and do not require a realizable model that connects input data and labels. 3) Our PGD algorithm is augmented to learn the bias terms which boosts the performance. The numerical experiments validate our theoretical results.

preprint2019arXiv

Performance Characterization of Canonical Mobility Models in Drone Cellular Networks

In this paper, we characterize the performance of several canonical mobility models in a drone cellular network in which drone base stations (DBSs) serve user equipments (UEs) on the ground. In particular, we consider the following four mobility models: (i) straight line (SL), (ii) random stop (RS), (iii) random walk (RW), and (iv) random waypoint (RWP), among which the SL mobility model is inspired by the simulation models used by the third generation partnership project (3GPP) for the placement and trajectory of drones, while the other three are well-known canonical models (or their variants) that offer a useful balance between realism and tractability. Assuming the nearest-neighbor association policy, we consider two service models for the UEs: (i) UE independent model (UIM), and (ii) UE dependent model (UDM). While the serving DBS follows the same mobility model as the other DBSs in the UIM, it is assumed to fly towards the UE of interest in the UDM and hover above its location after reaching there. The main contribution of this paper is a unified approach to characterize the point process of DBSs for all the mobility and service models. Using this, we provide exact mathematical expressions for the average received rate and the session rate as seen by the typical UE. Further, using tools from calculus of variations, we concretely demonstrate that the simple SL mobility model provides a lower bound on the performance of other general mobility models (including the ones in which drones follow curved trajectories) as long as the movement of each drone in these models is independent and identically distributed (i.i.d.). To the best of our knowledge, this is the first work that provides a rigorous analysis of key canonical mobility models for an infinite drone cellular network and establishes useful connections between them.

preprint2019arXiv

On the Information Privacy Model: the Group and Composition Privacy

How to query a dataset in the way of preserving the privacy of individuals whose data is included in the dataset is an important problem. The information privacy model, a variant of Shannon's information theoretic model to the encryption systems, protects the privacy of an individual by controlling the amount of information of the individual's data obtained by each adversary from the query's output. This model also assumes that each adversary's uncertainty to the queried dataset is not so small in order to improve the data utility. In this paper, we prove some results to the group privacy and the composition privacy properties of this model, where the group privacy ensures a group of individuals' privacy is preserved, and where the composition privacy ensures multiple queries also preserve the privacy of an individual. Explicitly, we reduce the proof of the two properties to the estimation of the difference of two channel capacities. Our proofs are greatly benefited from some information-theoretic tools and approaches.