Search

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}$ , $m\geq 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 $q\equiv 1\pmod {2}$ and $q\equiv 1\pmod {3}$ , show these upper bounds are tight and reachable; especially for $q=2\times 3^{\lambda }+1 (1\leq \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. [ABSTRACT FROM AUTHOR]

It is a well-known fact that the Discrete Fourier Transform (DFT) \vec X of an arbitrary n -length input signal \vec {x} , can be computed from all the n time-domain samples in O( n\log n) operations via a Fast Fourier Transform (FFT) algorithm. If the spectrum k -sparse (where k\ll n ), can we do better? We show that asymptotically in k and n , when k ), where 0 \leq \delta <1 ), and the support of the non-zero DFT coefficients is uniformly random, the fast fourier aliasing-based sparse transform (FFAST) algorithm, proposed in this paper, computes, with asymptotically high probability, the k non-zero DFT coefficients of from O( k) samples of \vec x in O( k\log k) arithmetic operations. Further, the constants in the big Oh notation for both sample and computational cost are small, e.g., when \delta < 0.99 , which essentially covers a wide range of sub-linear sparsity cases, the sample cost is less than 4 k . Although, in this paper we assume that the samples of the signal \vec x observed by the FFAST are noise-free, a noise-robust extension of the FFAST is provided in a companion (Part II) paper [1]. Our approach is based on filter-less sub-sampling of the input signal using a set of carefully chosen uniform sub-sampling patterns guided by the Chinese Remainder Theorem (CRT). The idea is to cleverly exploit, rather than avoid, the resulting aliasing artifacts induced by sub-sampling. Specifically, the sub-sampling operation on the time-domain signal \vec x is designed to create aliasing patterns of the non-zero coefficients of the spectrum \vec X to “look like” parity-check constraints of a good erasure-correcting sparse-graph code. Next, we show that computing the sparse DFT \vec X is equivalent to decoding of an appropriate sparse-graph code. The sparse-graph codes further permit a fast peeling-style decoding. Consequently, the resulting DFT computation is low in both the sample and the decoding complexity. We analytically connect our proposed CRT-based aliasing framework to random sparse-graph codes, and analyze the performance of our algorithm using density evolution techniques from coding theory. We provide extensive simulation results, that are in tight agreement with our theoretical findings. [ABSTRACT FROM PUBLISHER]

A generalized Chinese remainder theorem (CRT) for multiple integers from residue sets has been studied recently, where the correspondence between the remainders and the integers in each residue set modulo several moduli is not known. A robust CRT has also been proposed lately to robustly reconstruct a single integer from its erroneous remainders. In this paper, we consider the reconstruction problem of two integers from their residue sets, where the remainders not only are out of order but also may have errors. We prove that two integers can be robustly reconstructed if their remainder errors are less than $M/8$ , where $M$ is the greatest common divisor of all the moduli. We also propose an efficient reconstruction algorithm. Finally, we present some simulations to verify the efficiency of the proposed algorithm. This paper is motivated from and has applications in the determination of multiple frequencies from multiple undersampled waveforms. [ABSTRACT FROM PUBLISHER]

In this paper, we develop a technique to extend any bound for the minimum distance of cyclic codes constructed from its defining sets (ds-bounds) to Abelian (or multivariate) codes through the notion of ${\mathbb B}$ -apparent distance. We also study conditions for an Abelian code to verify that its ${\mathbb B}$ -apparent distance reaches its (true) minimum distance. Then, we construct some codes as an application. [ABSTRACT FROM AUTHOR]

The fast Fourier transform is the most efficiently known way to compute the discrete Fourier transform (DFT) of an arbitrary n -length signal, and has a computational complexity of O( n\log n) . If the DFT \vec X of the signal \vec x has only $k$ non-zero coefficients (where k< n$ ), can we do better? We addressed this question and presented a novel fast Fourier aliasing-based sparse transform (FFAST) algorithm that cleverly induces sparse-graph alias codes in the DFT domain, via a Chinese-remainder-theorem-guided sub-sampling operation in the time-domain. The induced sparse-graph alias codes are then exploited to devise a fast and iterative onion-peeling style decoder that computes k$ -sparse DFT of an n$ -length signal using only O( k)$ time-domain samples and O( k\log k)$ computations. In this paper, we generalize the FFAST framework by Pawar and Ramchandran to the noisy setting where the time-domain samples are corrupted by white Gaussian noise. We show that the noise-robust R-FFAST algorithm computes a k noise-corrupted time-domain samples in O( k\log ^{4} n) complexity, i.e., sub-linear sample and time complexity. In Section IX, we provide extensive simulation results validating the empirical performance of the R-FFAST algorithm, e.g., we show that the R-FFAST algorithm computes a 50-sparse DFT of an ≈ 10 million length signal using only 4800 noisy samples with an effective signal-to-noise ratio of 5 dB. We also provide comparison of the run-time performance of several existing sparse Fourier transform implementations with that of the R-FFAST and show that it is almost 20 times faster, for comparable settings, than the state-of-the-art algorithm, while simultaneously providing better support recovery guarantees. While our theoretical results are for signals with a uniformly random support of the non-zero DFT coefficients and additive white Gaussian noise, we provide simulation results, which demonstrate that the R-FFAST algorithm performs well even for signals like magnetic resonance images, that have an approximately sparse Fourier spectrum with a non-uniform support for the dominant DFT coefficients. [ABSTRACT FROM PUBLISHER]

Recently, Liu and Zhang studied the rather challenging problem of time series forecasting from the perspective of compressed sensing. They proposed a no-learning method, named Convolution Nuclear Norm Minimization (CNNM), and proved that CNNM can exactly recover the future part of a series from its observed part, provided that the series is convolutionally low-rank. While impressive, the convolutional low-rankness condition may not be satisfied whenever the series is far from being seasonal, and is in fact brittle to the presence of trends and dynamics. This paper tries to approach the issues by integrating a learnable, orthonormal transformation into CNNM, with the purpose for converting the series of involute structures into regular signals of convolutionally low-rank. We prove that the resultant model, termed Learning-Based CNNM (LbCNNM), strictly succeeds in identifying the future part of a series, as long as the transform of the series is convolutionally low-rank. To learn proper transformations that may meet the required success conditions, we devise an interpretable method based on Principal Component Pursuit (PCP). Equipped with this learning method and some elaborate data argumentation skills, LbCNNM not only can handle well the major components of time series (including trends, seasonality and dynamics), but also can make use of the forecasts provided by some other forecasting methods; this means LbCNNM can be used as a general tool for model combination. Extensive experiments on 100,452 real-world time series from Time Series Data Library (TSDL) and M4 Competition (M4) demonstrate the superior performance of LbCNNM. [ABSTRACT FROM AUTHOR]

Bilinear inverse problems (BIPs), the resolution of two vectors given their image under a bilinear mapping, arise in many applications. Without further constraints, BIPs are usually ill-posed. In practice, the properties of natural signals are exploited to solve BIPs. For example, subspace constraints or sparsity constraints are imposed to reduce the search space. These approaches have shown some success in practice. However, there are few results on uniqueness in BIPs. For most BIPs, the fundamental question of under what condition the problem admits a unique solution is yet to be answered. For example, blind gain and phase calibration (BGPC) is a structured BIP, which arises in many applications, including inverse rendering in computational relighting (albedo estimation with unknown lighting), blind phase and gain calibration in sensor array processing, and multichannel blind deconvolution (MBD). It is interesting to study the uniqueness of such problems. In this paper, we define identifiability of a BIP up to a group of transformations. We derive necessary and sufficient conditions for such identifiability, i.e., the conditions under which the solutions can be uniquely determined up to the transformation group. These conditions take the form of dividing the identifiability of the pair of unknown variables into the individual identifiability of each variable. Although verifying these individual conditions requires problem-specific procedures, this framework is universally applicable to all BIPs. Applying these results to BGPC, we derive sufficient conditions for unique recovery under several scenarios, including subspace, joint sparsity, and sparsity models. For BGPC with joint sparsity or sparsity constraints, we develop a procedure to compute the transformation groups corresponding to inherent ambiguities. We also give necessary conditions in the form of tight lower bounds on sample complexities, and demonstrate the tightness of these bounds by numerical experiments. The results for BGPC not only demonstrate the application of the proposed general framework for identifiability analysis, but are also of interest in their own right. [ABSTRACT FROM AUTHOR]

In the multireference alignment model, a signal is observed by the action of a random circular translation and the addition of Gaussian noise. The goal is to recover the signal’s orbit by accessing multiple independent observations. Of particular interest is the sample complexity, i.e., the number of observations/samples needed in terms of the signal-to-noise ratio (SNR) (the signal energy divided by the noise variance) in order to drive the mean-square error to zero. Previous work showed that if the translations are drawn from the uniform distribution, then, in the low SNR regime, the sample complexity of the problem scales as $\omega (1/ \mathrm {SNR}^{3})$. In this paper, using a generalization of the Chapman–Robbins bound for orbits and expansions of the $\chi ^{2}$ divergence at low SNR, we show that in the same regime the sample complexity for any aperiodic translation distribution scales as $\omega (1/ \mathrm {SNR}^{2})$. This rate is achieved by a simple spectral algorithm. We propose two additional algorithms based on non-convex optimization and expectation–maximization. We also draw a connection between the multireference alignment problem and the spiked covariance model. [ABSTRACT FROM AUTHOR]

In this paper, we provide a solution to the open problem of computing the Fourier transform of a binary function defined over n -bit vectors taking m -bit vector values. In particular, we introduce the two-modular Fourier transform (TMFT) of a binary function f:G\rightarrow \mathcal R , where G = (\mathbb F2^{n},+) is the group of n bit vectors with bitwise modulo two addition +, and {\mathcal{ R}} is a finite commutative ring of characteristic 2. Using the specific group structure of G and a sequence of nested subgroups of G , we define the fast TMFT and its inverse. Since the image {\mathcal{ R}} of the binary functions is a ring, we can define the convolution between two functions f:G\rightarrow {\mathcal{ R}}$ . We then provide the TMFT properties, including the convolution theorem, which can be used to efficiently compute convolutions. Finally, we derive the complexity of the fast TMFT and the inverse fast TMFT. [ABSTRACT FROM AUTHOR]

This paper is devoted to studying two main problems: 1) computing the apparent distance of an Abelian code and 2) giving a notion of Bose, Ray-Chaudhuri, Hocquenghem (BCH) multivariate code. To do this, we first strengthen the notion of an apparent distance by introducing the notion of a strong apparent distance; then, we present an algorithm to compute the strong apparent distance of an Abelian code, based on some manipulations of hypermatrices associated with its generating idempotent. Our method uses less computations than those given by Camion and Sabin; furthermore, in the bivariate case, the order of computation complexity is reduced from exponential to linear. Then, we use our techniques to develop a notion of a BCH code in the multivariate case, and we extend most of the classical results on cyclic BCH codes. Finally, we apply our method to the design of Abelian codes with maximum dimension with respect to a fixed apparent distance and a fixed length. [ABSTRACT FROM AUTHOR]

A composite number can be factored into either N=mp or N=2^{n} , where p$ is an odd prime and m$ , n\geq 2$ are integers. This paper proposes a method for constructing degree-3 and degree-4 perfect Gaussian integer sequences (PGISs) of an arbitrary composite length utilizing an upsampling technique and the base sequence concept proposed by Hu, Wang, and Li. In constructing the PGISs, the degree of the sequence is defined as the number of distinct nonzero elements within one period of the sequence. This paper commences by constructing degree-3 PGISs of odd prime length, followed by degree-2 PGISs of odd prime length. The proposed method is then extended to the construction of degree-3 and degree-4 PGISs of composite length N=mp$ . Finally, degree-3 and degree-4 PGISs of length N=4 , where $n\geq 3$ . [ABSTRACT FROM PUBLISHER]

The Walsh transform \(\widehat {f}\) of a quadratic function \(f: {\mathbb F}_{p^{n}}\rightarrow {\mathbb F} _{p}\) satisfies \(|\widehat {f}| \in \{0,p^{{n+s}/{2}}\}\) for an integer \(0\le s\le n-1\) , depending on \(f\) . In this paper, quadratic functions of the form \({\mathcal {F}}_{p,n}(x) = {\rm Tr_{n}}(\sum _{i=0}^{k}a_{i}x^{p^{i}+1})\) are studied, with the restriction that \(a_{i} \in {\mathbb F} _{p},~ 0\leq i\leq k\) . Three methods for enumeration of such functions are presented when the value for \(s\) is prescribed. This paper extends earlier enumeration results significantly, for instance, the generating function for the counting function is obtained, when \(n\) is odd and relatively prime to \(p\) , or when \(n=2m\) , for odd \(m\) and \(p=2.\) The number of bent and semibent functions for various classes of \(n\) is also obtained [ABSTRACT FROM AUTHOR]

This paper considers recovering L -dimensional vectors {w} , and {x}_{1}, {x}_{2}, \ldots, {x}_{N} from their circular convolutions yn = {w}* {x}n, \,\,n = 1,2,3, \ldots, N . The vector {w} is assumed to be S -sparse in a known basis that is spread out in the Fourier domain, and each input {x}_{n} is a member of a known K -dimensional random subspace. We prove that whenever K + S\log ^2S \lesssim L /\log ^4(LN) , the problem can be solved effectively by using only the nuclear-norm minimization as the convex relaxation, as long as the inputs are sufficiently diverse and obey N \gtrsim \log ^2(LN) . By “diverse inputs,” we mean that the xn ’s belong to different, generic subspaces. To the best of our knowledge, this is the first theoretical result on blind deconvolution where the subspace to which w belongs is not fixed but needs to be determined. We discuss the result in the context of multipath channel estimation in wireless communications. Both the fading coefficients and the delays in the channel impulse response w are unknown. The encoder codes the K -dimensional message vectors randomly and then transmits coded messages (K+S\log ^{2}S)\log ^{4}(LN) , and the number of messages is roughly at least \log ^{2}(LN)$ . [ABSTRACT FROM PUBLISHER]

Much of the existing literature in sparse recovery is concerned with the following question: given a sparsity pattern and a corresponding regularizer, derive conditions on the dictionary under which exact recovery is possible. In this paper, we study the opposite question: given a dictionary and the ℓ1-norm regularizer, find the largest sparsity pattern that can be recovered. We show that such a pattern is described by a mathematical object called a “maximum abstract simplicial complex,” and provide two different characterizations of this object: one based on extreme points and the other based on vectors of minimal support. In addition, we show how this new framework is useful in the study of sparse recovery problems when the dictionary takes the form of a graph incidence matrix or a partial discrete Fourier transform. In case of incidence matrices, we show that the largest sparsity pattern that can be recovered is determined by the set of simple cycles of the graph. As a byproduct, we show that standard sparse recovery can be certified in polynomial time, although this is known to be NP-hard for general matrices. In the case of the partial discrete Fourier transform, our characterization of the largest sparsity pattern that can be recovered requires the unknown signal to be real and its dimension to be a prime number. [ABSTRACT FROM AUTHOR]

An equiangular tight frame (ETF) yields a type of optimal packing of lines in a Euclidean space. ETFs seem to be rare, and all known infinite families of them arise from some type of combinatorial design. In this paper, we introduce a new method for constructing ETFs. We begin by showing that it is sometimes possible to construct multiple ETFs for the same space that are “mutually unbiased” in a way that is analogous to the quantum-information-theoretic concept of mutually unbiased bases. We then show that taking certain tensor products of these mutually unbiased ETFs with other ETFs sometimes yields infinite families of new complex ETFs. [ABSTRACT FROM AUTHOR]

The discrete Fourier transform test is a randomness test included in NIST SP800-22. However, the variance of the test statistic is smaller than expected and the theoretical value of the variance is not known. Hitherto, the mechanism explaining why the former variance is smaller than expected has been qualitatively explained based on Parseval’s theorem. In this paper, we explore this quantitatively and derive the variance using Parseval’s theorem under particular assumptions. Numerical experiments are then used to show that this derived variance is robust. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a sequence of discrete Fourier transforms and define new versions of bent functions, which we shall call (weak and strong) octa/hexadeca and, in general, 2^k -bent functions. We investigate relationships between these classes and completely characterize the octabent and hexadecabent functions in terms of bent functions. We further find relative difference sets based upon these functions. [ABSTRACT FROM AUTHOR]

Recently, symbol-pair codes are proposed to protect against pair errors in symbol-pair read channels. One main task in symbol-pair coding theory is to design codes with large minimum pair distance. Maximum distance separable (MDS) symbol-pair codes are optimal in the sense they attain maximal minimum pair distance. In this paper, based on constacyclic codes, we construct some new MDS symbol-pair codes with minimum pair-distance five and six. Compared with classical $q$ -ary MDS codes, the constructed MDS symbol-pair codes have length up to q^{2}+q+1 . [ABSTRACT FROM PUBLISHER]

Partial-period correlations of sequences are an important performance measure of communication systems employing them, but are known to be notoriously difficult to analyze. In this paper, we present a systematic approach to partial-period correlations as a generalization of the Paterson–Lothian approach. For a pair of sequences (not necessarily distinct), we introduce the linear phase-shifting sequences of one of them and analyze their full-period correlations, called the induced correlations, with the other one. By exploiting the induced correlations, we obtain the partial-period correlation properties of the given pair. We then investigate Zadoff–Chu sequences, and give some theoretical results on their partial-period autocorrelations, including closed-form expressions, and the first and second moments. We also derive an upper bound on the magnitudes of the partial-period cross-correlations of Zadoff–Chu sequences. Finally, we explore generalized chirp-like discrete Fourier transform sequences and show that their partial-period cross-correlations have the same magnitudes as the partial-period autocorrelations of the employed Zadoff–Chu sequence up to permutation. [ABSTRACT FROM AUTHOR]

Symbol-pair codes introduced by Cassuto and Blaum (2010) are designed to protect against pair errors in symbol-pair read channels. The higher the minimum pair distance, the more pair errors the code can correct. Maximum distance separable (MDS) symbol-pair codes are optimal in the sense that pair distance cannot be improved for given length and code size. The contribution of this paper is twofold. First, we present three lower bounds for the minimum pair distance of constacyclic codes, the first two of which generalize the previously known results due to Cassuto and Blaum (2011) and Kai et al. (2015). The third one exhibits a lower bound for the minimum pair distance of repeated-root cyclic codes. Second, we obtain new MDS symbol-pair codes with minimum pair distance seven and eight through repeated-root cyclic codes. [ABSTRACT FROM AUTHOR]

In this paper, we present a fast Fourier transform algorithm over extension binary fields, where the polynomial is represented in a non-standard basis. The proposed Fourier-like transform requires \mathcal O(h\lg (h)) field operations, where h is the number of evaluation points. Based on the proposed Fourier-like algorithm, we then develop the encoding/decoding algorithms for (n=2^{m},k) Reed–Solomon erasure codes. The proposed encoding/erasure decoding algorithm requires \mathcal {O}(n\lg (n))$ , in both additive and multiplicative complexities. As the complexity leading factor is small, the proposed algorithms are advantageous in practical applications. Finally, the approaches to convert the basis between the monomial basis and the new basis are proposed. [ABSTRACT FROM AUTHOR]

The problem of recovering a one-dimensional signal from its Fourier transform magnitude, called Fourier phase retrieval, is ill-posed in most cases. We consider the closely-related problem of recovering a signal from its phaseless short-time Fourier transform (STFT) measurements. This problem arises naturally in several applications, such as ultra-short laser pulse characterization and ptychography. The redundancy offered by the STFT enables unique recovery under mild conditions. We show that in some cases the unique solution can be obtained by the principal eigenvector of a matrix, constructed as the solution of a simple least-squares problem. When these conditions are not met, we suggest using the principal eigenvector of this matrix to initialize non-convex local optimization algorithms and propose two such methods. The first is based on minimizing the empirical risk loss function, while the second maximizes a quadratic function on the manifold of phases. We prove that under appropriate conditions, the proposed initialization is close to the underlying signal. We then analyze the geometry of the empirical risk loss function and show numerically that both gradient algorithms converge to the underlying signal even with small redundancy in the measurements. In addition, the algorithms are robust to noise. [ABSTRACT FROM PUBLISHER]

One problem with multiple access channel (MAC) polar codes that are based on MAC polarization is that they may not achieve the entire capacity region. The reason behind this problem is that MAC polarization sometimes induces a loss in the capacity region. This paper provides a single letter necessary and sufficient condition, which characterizes all the MACs that do not lose any part of their capacity region by polarization. [ABSTRACT FROM AUTHOR]

In the phase retrieval problem one seeks to recover an unknown $n$ dimensional signal vector $\mathbf {x}$ from $m$ measurements of the form $y_{i} = |(\mathbf {A} \mathbf {x})_{i}|$ , where $\mathbf {A}$ denotes the sensing matrix. Many algorithms for this problem are based on approximate message passing. For these algorithms, it is known that if the sensing matrix $\mathbf {A}$ is generated by sub-sampling $n$ columns of a uniformly random (i.e., Haar distributed) orthogonal matrix, in the high dimensional asymptotic regime ($m,n \rightarrow \infty, n/m \rightarrow \kappa $), the dynamics of the algorithm are given by a deterministic recursion known as the state evolution. For a special class of linearized message-passing algorithms, we show that the state evolution is universal: it continues to hold even when $\mathbf {A}$ is generated by randomly sub-sampling columns of the Hadamard-Walsh matrix, if the signal is drawn from a Gaussian prior. [ABSTRACT FROM AUTHOR]

A fundamental challenge in learning is the presence of nonlinear redundancies and dependencies in the data. To address this, we propose a Fourier-based approach to characterize feature redundancies, in unsupervised learning, and feature-label dependencies, in the supervised variant of the problem. We first develop a novel Fourier expansion for functions (more generally stochastic mappings) of correlated binary random variables. This is a generalization of the standard Fourier expansion on the Boolean cube beyond product probability spaces. As an important application of this analysis, we investigate learning with feature subset selection. In the unsupervised variant of this problem, we characterize feature redundancies via the Shannon entropy and group the features into sufficiently informative and redundant. Then, we make a connection to the proposed Fourier expansion and derive an upper bound on the joint entropy. Based on that, we propose a measure to quantify feature redundancies and present an unsupervised learning algorithm. We test our method on various real-world and synthetic datasets and demonstrate improvements on conventional unsupervised feature selection techniques. Then, we investigate the supervised feature subset selection and reformulate it in the Fourier domain. Bridging the Bayesian error rate with the Fourier coefficients, we demonstrate that the Fourier expansion provides a powerful tool to characterize nonlinear feature-label dependencies. Further, we introduce a computationally efficient measure for selecting relevant features. Via a theoretical analysis, we show that our proposed measure finds provably asymptotically optimal feature subsets. Lastly, we present an algorithm based on this measure and via numerical experiments demonstrate its improvements on various supervised feature selection algorithms. [ABSTRACT FROM AUTHOR]

Using elementary properties of primitive multiplicative characters we derive the autocorrelation of a unimodular $M$ -ary character-based sequence of length $pq$ , where $p$ and $q$ are distinct odd primes. Subsequently: (1) we identify three new sets of twin-prime quadriphase sequences with the largest autocorrelation sidelobe magnitude equal to $\sqrt {5}$ or 3, (2) we show that the smallest maximum autocorrelation sidelobe magnitude of an $M$ -ary character-based sequence, when $4|M$ , either decreases with $M$ and tends to 2, when $6\nmid M$ , or is equal to 2, when $6|M$ , and (3), we show that the smallest maximum autocorrelation sidelobe magnitude of a full-alphabet $M$ -ary character-based sequence, where $M>2$ , is greater or equal to $\sqrt {3}$ , and, in particular, is equal to $\sqrt {3}$ for the sextic phase sequence. [ABSTRACT FROM AUTHOR]

We consider the problem of secure distributed matrix computation (SDMC), where a user queries a function of data matrices generated at distributed source nodes. We assume the availability of $N$ honest but curious computation servers, which are connected to the sources, the user, and each other through orthogonal and reliable communication links. Our goal is to minimize the amount of data that must be transmitted from the sources to the servers, called the upload cost, while guaranteeing that no $T$ colluding servers can learn any information about the source matrices, and the user cannot learn any information beyond the computation result. We first focus on secure distributed matrix multiplication (SDMM), considering two matrices, and propose a novel polynomial coding scheme using the properties of finite field discrete Fourier transform, which achieves an upload cost significantly lower than the existing results in the literature. We then generalize the proposed scheme to include straggler mitigation, and to the multiplication of multiple matrices while keeping the input matrices, the intermediate computation results, as well as the final result secure against any $T$ colluding servers. We also consider a special case, called computation with own data, where the data matrices used for computation belong to the user. In this case, we drop the security requirement against the user, and show that the proposed scheme achieves the minimal upload cost. We then propose methods for performing other common matrix computations securely on distributed servers, including changing the parameters of secret sharing, matrix transpose, matrix exponentiation, solving a linear system, and matrix inversion, which are then used to show how arbitrary matrix polynomials can be computed securely on distributed servers using the proposed procedure. [ABSTRACT FROM AUTHOR]

The algebraic formulation for linear network coding in acyclic networks with the links having integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes, at any given time instant, is a \(\mathbb {F}_{p^{m}}\) -linear combination of the input symbols across different generations, where \(\mathbb {F}_{p^{m}}\) denotes the field over which the network operates ( \(p\) is prime and \(m\) is a positive integer). We use finite-field discrete Fourier transform to convert the output symbols at the sink nodes, at any given time instant, into a \(\mathbb {F}_{p^{m}}\) -linear combination of the input symbols generated during the same generation without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into \(n\) -instantaneous networks ( \(n\) is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (nontransform) approach if and only if there exists a network code satisfying sink demands in the transform approach. When the zero-interference conditions are not satisfied, we propose three precoding-based network alignment (PBNA) schemes for three-source three-destination multiple unicast network with delays (3-S 3-D MUN-D) termed as PBNA using transform approach and time-invariant local encoding coefficients (LECs), PBNA using time-varying LECs, and PBNA using transform approach and block time-varying LECs. We derive sets of necessary and sufficient conditions under which throughputs close to \({n'+1}/{2n'+1}\) , \({n'}/{2n'+1}\) , and \({n'}/{2n'+1}\) are achieved for the three source–destination pairs in a 3-S 3-D MUN-D employing PBNA using transform approach and time-invariant LECs, and PBNA using transform approach and block time-varying LECs, where \(n'\) is a positive integer. For PBNA using time-varying LECs, we obtain a sufficient condition under which a throughput demand of \({n_{1}}/{n}\) , \({n_{2}}/{n}\) , and \({n_{3}}/{n}\) can be met for the three source-destination pairs in a 3-S 3-D MUN-D, where \(n_{1}\) , \(n_{2}\) , and \(n_{3}\) are positive integers less than or equal to the positive integer \(n\) . This condition is also necessary when \(n_{1}+n_{3}=n_{1}+n_{2}=n\) where \(n_{1} \geq n_{2} \geq n_{3}\) . [ABSTRACT FROM AUTHOR]

The capacity of a relay channel with intersymbol interference (ISI) and additive colored Gaussian noise is examined under an input power constraint. Prior results are used to show that the capacity of this channel can be computed by examining the circular degraded relay channel in the limit of infinite block length. The current work provides single letter expressions for the achievable rates with decode-and-forward (DF) and compress-and-forward (CF) processing employed at the relay. Additionally, the cut-set bound for the relay channel is generalized for the ISI/colored Gaussian noise scenario. All results hinge on showing the optimality of the decomposition of the relay channel with ISI/colored Gaussian noise into an equivalent collection of coupled parallel, scalar, memoryless relay channels. The region of optimality of the DF and CF achievable rates is also discussed. The resulting rates are illustrated through the computation of numerical examples. [ABSTRACT FROM AUTHOR]

We study the dihedral multi-reference alignment problem of estimating the orbit of a signal from multiple noisy observations of the signal, acted on by random elements of the dihedral group. We show that if the group elements are drawn from a generic distribution, the orbit of a generic signal is uniquely determined from the second moment of the observations. This implies that the optimal estimation rate in the high noise regime is proportional to the square of the variance of the noise. This is the first result of this type for multi-reference alignment over a non-abelian group with a non-uniform distribution of group elements. Based on tools from invariant theory and algebraic geometry, we also delineate conditions for unique orbit recovery for multi-reference alignment models over finite groups (namely, when the dihedral group is replaced by a general finite group) when the group elements are drawn from a generic distribution. Finally, we design and study numerically three computational frameworks for estimating the signal based on group synchronization, expectation-maximization, and the method of moments. [ABSTRACT FROM AUTHOR]

We study information theoretic limits of recovering an unknown ${n}$ dimensional, complex signal vector ${x}_{\star} $ with unit norm from ${m}$ magnitude-only measurements of the form ${y}_{i} = |({A}{x}_{\star})_{i}|^{2}, \; {i} = 1,2 {\dots }, {m}$ , where ${A}$ is the sensing matrix. This is known as the Phase Retrieval problem and models practical imaging systems where measuring the phase of the observations is difficult. Since in a number of applications, the sensing matrix has orthogonal columns, we model the sensing matrix as a subsampled Haar matrix formed by picking ${n}$ columns of a uniformly random ${m} \times {m}$ unitary matrix. We study this problem in the high dimensional asymptotic regime, where ${m},{n} \rightarrow \infty $ , while ${m}/{n} \rightarrow \delta $ with $\delta $ being a fixed number, and show that if ${m} < (2-{o}_{n}(1))\cdot {n}$ , then any estimator is asymptotically orthogonal to the true signal vector ${x}_{\star} $. This lower bound is sharp since when ${m} > (2+{o}_{n}(1)) \cdot {n} $ , estimators that achieve a non trivial asymptotic correlation with the signal vector are known from previous works. [ABSTRACT FROM AUTHOR]

In the sparse polynomial multiplication problem, one is asked to multiply two sparse polynomials $f$ and $g$ in time that is proportional to the size of the input plus the size of the output. The polynomials are given via lists, $F$ and $G$ , of their coefficients. Cole and Hariharan (STOC 02) have given a nearly optimal algorithm when the coefficients are positive, and Arnold and Roche (ISSAC 15) devised an algorithm running in time proportional to the “structural sparsity” of the product, i.e. the set $\mathrm {supp}(F) + \mathrm {supp}(G)$. The latter algorithm is particularly efficient when there are not “too many cancellations” of coefficients in the product. In this work we give a clean, nearly optimal algorithm for the sparse polynomial multiplication problem. [ABSTRACT FROM AUTHOR]

We study the Low Rank Phase Retrieval (LRPR) problem defined as follows: recover an $n \times q$ matrix ${ \boldsymbol {X}^{*}}$ of rank $r$ from a different and independent set of $m$ phaseless (magnitude-only) linear projections of each of its columns. To be precise, we need to recover ${ \boldsymbol {X}^{*}}$ from $\boldsymbol {y}_{k}:= | \boldsymbol {A}_{k}{}' \boldsymbol {x}^{*}_{k}|, k=1,2, {\dots }, q$ when the measurement matrices $\boldsymbol {A}_{k}$ are mutually independent. Here $\boldsymbol {y}_{k}$ is an $m$ length vector, $\boldsymbol {A}_{k}$ is an $n \times m$ matrix, and $'$ denotes matrix transpose. The question is when can we solve LRPR with $m \ll n$ ? A reliable solution can enable fast and low-cost phaseless dynamic imaging, e.g., Fourier ptychographic imaging of live biological specimens. In this work, we develop the first provably correct approach for solving this LRPR problem. Our proposed algorithm, Alternating Minimization for Low-Rank Phase Retrieval (AltMinLowRaP), is an AltMin based solution and hence is also provably fast (converges geometrically). Our guarantee shows that AltMinLowRaP solves LRPR to $\epsilon $ accuracy, with high probability, as long as $m q \ge C n r^{4} \log (1/\epsilon)$ , the matrices $\boldsymbol {A}_{k}$ contain i.i.d. standard Gaussian entries, and the right singular vectors of ${ \boldsymbol {X}^{*}}$ satisfy the incoherence assumption from matrix completion literature. Here $C$ is a numerical constant that only depends on the condition number of ${ \boldsymbol {X}^{*}}$ and on its incoherence parameter. Its time complexity is only $C mq nr \log ^{2}(1/\epsilon)$. Since even the linear (with phase) version of the above problem is not fully solved, the above result is also the first complete solution and guarantee for the linear case. Finally, we also develop a simple extension of our results for the dynamic LRPR setting. [ABSTRACT FROM AUTHOR]

We study the problem of finding unitary submatrices of the $N \times N$ discrete Fourier transform matrix, in the context of interpolating a discrete bandlimited signal using an orthogonal basis. This problem is related to a diverse set of questions on idempotents on $\mathbb {Z}_{N}$ and tiling $\mathbb {Z}_{N}$. In this work, we establish a graph-theoretic approach and connections to the problem of finding maximum cliques. We identify the key properties of these graphs that make the interpolation problem tractable when $N$ is a prime power, and we identify the challenges in generalizing to arbitrary $N$. Finally, we investigate some connections between graph properties and the spectral-tile direction of the Fuglede conjecture. [ABSTRACT FROM AUTHOR]

Let (I,+) be a finite abelian group and \mathbf {A} be a circular convolution operator on \ell ^{2}(I) . The problem under consideration is how to construct minimal \Omega \subset I and l_{i} such that Y=\{\mathbf {e}_{i}, \mathbf {A}\mathbf {e}_{i}, \cdots , \mathbf {A}^{l_{i}}\mathbf {e}_{i}: i\in \Omega \} is a frame for \ell ^2(I) , where \\mathbf ei: i\in I\ is the canonical basis of \ell ^2(I) . This problem is motivated by the spatiotemporal sampling problem in discrete spatially invariant evolution processes. We will show that the cardinality of \Omega should be at least equal to the largest geometric multiplicity of eigenvalues of \mathbf {A} , and consider the universal spatiotemporal sampling sets (\Omega , l_{i})$ for convolution operators whose eigenvalues subject to the same largest geometric multiplicity. We will give an algebraic characterization for such sampling sets and show how this problem is linked with sparse signal processing theory and polynomial interpolation theory. [ABSTRACT FROM AUTHOR]