BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Jinming Wen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
Information Theorymath.IT

Catalog footprint

Research overview

12works
2topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

12 publications

preprint2022arXiv

Sharper Bounds on Four Lattice Constants

The Korkine--Zolotareff (KZ) reduction, and its generalisations, are widely used lattice reduction strategies in communications and cryptography. The KZ constant and Schnorr's constant were defined by Schnorr in 1987. The KZ constant can be used to quantify some useful properties of KZ reduced matrices. Schnorr's constant can be used to characterize the output quality of his block 2k2k-reduction and is used to define his semi block 2k2k-reduction, which was also developed in 1987. Hermite's constant, which is a fundamental constant lattices, has many applications, such as bounding the length of the shortest nonzero lattice vector and the orthogonality defect of lattices. Rankin's constant was introduced by Rankin in 1953 as a generalization of Hermite's constant. It plays an important role in characterizing the output quality of block-Rankin reduction, proposed by Gama et al. in 2006. In this paper, we first develop a linear upper bound on Hermite's constant and then use it to develop an upper bound on the KZ constant. These upper bounds are sharper than those obtained recently by the authors, and the ratio of the new linear upper bound to the nonlinear upper bound, developed by Blichfeldt in 1929, on Hermite's constant is asymptotically 1.0047. Furthermore, we develop lower and upper bounds on Schnorr's constant. The improvement to the lower bound over the sharpest existing one developed by Gama et al. is around 1.7 times asymptotically, and the improvement to the upper bound over the sharpest existing one which was also developed by Gama et al. is around 4 times asymptotically. Finally, we develop lower and upper bounds on Rankin's constant. The improvements of the bounds over the sharpest existing ones, also developed by Gama et al., are exponential in the parameter defining the constant.

Open access
preprint2020arXiv

Signal-Dependent Performance Analysis of Orthogonal Matching Pursuit for Exact Sparse Recovery

Exact recovery of KK-sparse signals x∈Rnx \in \mathbb{R}^{n} from linear measurements y=Axy=Ax, where A∈Rm×nA\in \mathbb{R}^{m\times n} is a sensing matrix, arises from many applications. The orthogonal matching pursuit (OMP) algorithm is widely used for reconstructing xx. A fundamental question in the performance analysis of OMP is the characterizations of the probability of exact recovery of xx for random matrix AA and the minimal mm to guarantee a target recovery performance. In many practical applications, in addition to sparsity, xx also has some additional properties. This paper shows that these properties can be used to refine the answer to the above question. In this paper, we first show that the prior information of the nonzero entries of xx can be used to provide an upper bound on ∥x∥12/∥x∥22\|x\|_1^2/\|x\|_2^2. Then, we use this upper bound to develop a lower bound on the probability of exact recovery of xx using OMP in KK iterations. Furthermore, we develop a lower bound on the number of measurements mm to guarantee that the exact recovery probability using KK iterations of OMP is no smaller than a given target probability. Finally, we show that when K=O(ln⁡n)K=O(\sqrt{\ln n}), as both nn and KK go to infinity, for any 0<ζ≤1/π0<ζ\leq 1/\sqrtπ, m=2Kln⁡(n/ζ)m=2K\ln (n/ζ) measurements are sufficient to ensure that the probability of exact recovering any KK-sparse xx is no lower than 1−ζ1-ζ with KK iterations of OMP. For KK-sparse αα-strongly decaying signals and for KK-sparse xx whose nonzero entries independently and identically follow the Gaussian distribution, the number of measurements sufficient for exact recovery with probability no lower than 1−ζ1-ζ reduces further to m=(K+4α+1α−1ln⁡(n/ζ))2m=(\sqrt{K}+4\sqrt{\frac{α+1}{α-1}\ln(n/ζ)})^2 and asymptotically m≈1.9Kln⁡(n/ζ)m\approx 1.9K\ln (n/ζ), respectively.

Open access
preprint2016arXiv

A Novel Sufficient Condition for Generalized Orthogonal Matching Pursuit

Generalized orthogonal matching pursuit (gOMP), also called orthogonal multi-matching pursuit, is an extension of OMP in the sense that N≥1N\geq1 indices are identified per iteration. In this paper, we show that if the restricted isometry constant (RIC) δNK+1δ_{NK+1} of a sensing matrix $\A$ satisfies δNK+1<1/K/N+1δ_{NK+1} < 1/\sqrt {K/N+1}, then under a condition on the signal-to-noise ratio, gOMP identifies at least one index in the support of any KK-sparse signal $\x$ from $\y=\A\x+\v$ at each iteration, where $\v$ is a noise vector. Surprisingly, this condition does not require N≤KN\leq K which is needed in Wang, \textit{et al} 2012 and Liu, \textit{et al} 2012. Thus, NN can have more choices. When N=1N=1, it reduces to be a sufficient condition for OMP, which is less restrictive than that proposed in Wang 2015. Moreover, in the noise-free case, it is a sufficient condition for accurately recovering $\x$ in KK iterations which is less restrictive than the best known one. In particular, it reduces to the sharp condition proposed in Mo 2015 when N=1N=1.

Open access
preprint2016arXiv

A Quadratic Programming Relaxation Approach to Compute-and-Forward Network Coding Design

Using physical layer network coding, compute-and-forward is a promising relaying scheme that effectively exploits the interference between users and thus achieves high rates. In this paper, we consider the problem of finding the optimal integer-valued coefficient vector for a relay in the compute-and-forward scheme to maximize the computation rate at that relay. Although this problem turns out to be a shortest vector problem, which is suspected to be NP-hard, we show that it can be relaxed to a series of equality-constrained quadratic programmings. The solutions of the relaxed problems serve as real-valued approximations of the optimal coefficient vector, and are quantized to a set of integer-valued vectors, from which a coefficient vector is selected. The key to the efficiency of our method is that the closed-form expressions of the real-valued approximations can be derived with the Lagrange multiplier method. Numerical results demonstrate that compared with the existing methods, our method offers comparable rates at an impressively low complexity.

Open access
preprint2016arXiv

An Efficient Algorithm for Optimally Solving a Shortest Vector Problem in Compute-and-Forward Protocol Design

We consider the problem of finding the optimal coefficient vector that maximizes the computation rate at a relay in the compute-and-forward scheme. Based on the idea of sphere decoding, we propose a highly efficient algorithm that finds the optimal coefficient vector. First, we derive a novel algorithm to transform the original quadratic form optimization problem into a shortest vector problem (SVP) using the Cholesky factorization. Instead of computing the Cholesky factor explicitly, the proposed algorithm realizes the Cholesky factorization with only $\bigO(n)$ flops by taking advantage of the structure of the Gram matrix in the quadratic form. Then, we propose some conditions that can be checked with $\bigO(n)$ flops, under which a unit vector is the optimal coefficient vector. Finally, by taking into account some useful properties of the optimal coefficient vector, we modify the Schnorr-Euchner search algorithm to solve the SVP. We show that the estimated average complexity of our new algorithm is $\bigO(n^{1.5}P^{0.5})$ flops for i.i.d. Gaussian channel entries with SNR PP based on the Gaussian heuristic. Simulations show that our algorithm is not only much more efficient than the existing ones that give the optimal solution, but also faster than some best known suboptimal methods. Besides, we show that our algorithm can be readily adapted to output a list of LL best candidate vectors for use in the compute-and-forward design. The estimated average complexity of the resultant list-output algorithm is $\bigO\left(n^{1.5}P^{0.5}\log L + nL\right)$ flops for i.i.d. Gaussian channel entries.

Open access
preprint2016arXiv

Joint Antenna Selection and Spatial Switching for Energy Efficient MIMO SWIPT System

In this paper, we investigate joint antenna selection and spatial switching (SS) for quality-of-service (QoS)-constrained energy efficiency (EE) optimization in a multiple-input multiple-output (MIMO) simultaneous wireless information and power transfer (SWIPT) system. A practical linear power model taking into account the entire transmit-receive chain is accordingly utilized. The corresponding fractional-combinatorial and non-convex EE problem, involving joint optimization of eigen-channel assignment, power allocation, and active receive antenna set selection, subject to satisfying minimum sum-rate and power transfer constraints, is extremely difficult to solve directly. In order to tackle this, we separate the eigen-channel assignment and power allocation procedure with the antenna selection functionality. In particular, we first tackle the EE maximization problem under fixed receive antenna set using Dinkelbach-based convex programming, iterative joint eigen-channel assignment and power allocation, and low-complexity multi-objective optimization (MOO)-based approach. On the other hand, the number of active receive antennas induces a trade-off in the achievable sum-rate and power transfer versus the transmit-independent power consumption. We provide a fundamental study of the achievable EE with antenna selection and accordingly develop dynamic optimal exhaustive search and Frobenius-norm-based schemes. Simulation results confirm the theoretical findings and demonstrate that the proposed resource allocation algorithms can efficiently approach the optimal EE.

Open access
preprint2016arXiv

Success probability of the Babai estimators for box-constrained integer linear models

In many applications including communications, one may encounter a linear model where the parameter vector $\hbx$ is an integer vector in a box. To estimate $\hbx$, a typical method is to solve a box-constrained integer least squares (BILS) problem. However, due to its high complexity, the box-constrained Babai integer point $\x^\sBB$ is commonly used as a suboptimal solution. In this paper, we first derive formulas for the success probability $P^\sBB$ of $\x^\sBB$ and the success probability $P^\sOB$ of the ordinary Babai integer point $\x^\sOB$ when $\hbx$ is uniformly distributed over the constraint box. Some properties of $P^\sBB$ and $P^\sOB$ and the relationship between them are studied. Then, we investigate the effects of some column permutation strategies on $¶^\sBB$. In addition to V-BLAST and SQRD, we also consider the permutation strategy involved in the LLL lattice reduction, to be referred to as LLL-P. On the one hand, we show that when the noise is relatively small, LLL-P always increases $P^\sBB$ and argue why both V-BLAST and SQRD often increase $P^\sBB$; and on the other hand, we show that when the noise is relatively large, LLL-P always decreases $P^\sBB$ and argue why both V-BLAST and SQRD often decrease $P^\sBB$. We also derive a column permutation invariant bound on $P^\sBB$, which is an upper bound and a lower bound under these two opposite conditions, respectively. Numerical results demonstrate our findings. Finally, we consider a conjecture concerning $\x^\sOB$ proposed by Ma et al. We first construct an example to show that the conjecture does not hold in general, and then show that it does hold under some conditions.

Open access
preprint2014arXiv

Effects of the LLL reduction on the success probability of the Babai point and on the complexity of sphere decoding

The common method to estimate an unknown integer parameter vector in a linear model is to solve an integer least squares (ILS) problem. A typical approach to solving an ILS problem is sphere decoding. To make a sphere decoder faster, the well-known LLL reduction is often used as preprocessing. The Babai point produced by the Babai nearest plan algorithm is a suboptimal solution of the ILS problem. First we prove that the success probability of the Babai point as a lower bound on the success probability of the ILS estimator is sharper than the lower bound given by Hassibi and Boyd [1]. Then we show rigorously that applying the LLL reduction algorithm will increase the success probability of the Babai point. Finally we show rigorously that applying the LLL reduction algorithm will also reduce the computational complexity of sphere decoders, which is measured approximately by the number of nodes in the search tree in the literature

Open access
preprint2014arXiv

Improved Bounds on the Restricted Isometry Constant for Orthogonal Matching Pursuit

In this letter, we first construct a counter example to show that for any given positive integer K≥2K\geq 2 and for any 1K+1≤t<1\frac{1}{\sqrt{K+1}}\leq t<1, there always exist a K−K-sparse $\x$ and a matrix $\A$ with the restricted isometry constant δK+1=tδ_{K+1}=t such that the OMP algorithm fails in KK iterations. Secondly, we show that even when δK+1=1K+1δ_{K+1}=\frac{1}{\sqrt{K}+1}, the OMP algorithm can also perfectly recover every K−K-sparse vector $\x$ from $\y=\A\x$ in KK iteration. This improves the best existing results which were independently given by Mo et al. and Wang et al.

Open access
preprint2014arXiv

Stable Recovery of Sparse Signals via lp−l_p-Minimization

In this paper, we show that, under the assumption that $\|\e\|_2\leq ε$, every k−k-sparse signal $\x\in \mathbb{R}^n$ can be stably (ε≠0ε\neq0) or exactly recovered (ε=0ε=0) from $\y=\A\x+\e$ via lp−l_p-mnimization with p∈(0,pˉ]p\in(0, \bar{p}], where \beqnn \bar{p}= \begin{cases} \frac{50}{31}(1-δ_{2k}), &δ_{2k}\in[\frac{\sqrt{2}}{2}, 0.7183)\cr 0.4541, &δ_{2k}\in[0.7183,0.7729)\cr 2(1-δ_{2k}), &δ_{2k}\in[0.7729,1) \end{cases}, \eeqnn even if the restricted isometry constant of $\A$ satisfies δ2k∈[22,1)δ_{2k}\in[\frac{\sqrt{2}}{2}, 1). Furthermore, under the assumption that n≤4kn\leq 4k, we show that the range of pp can be further improved to p∈(0,3+222(1−δ2k)]p\in(0,\frac{3+2\sqrt{2}}{2}(1-δ_{2k})]. This not only extends some discussions of only the noiseless recovery (Lai et al. and Wu et al.) to the noise recovery, but also greatly improves the best existing results where p∈(0,min⁡{1,1.0873(1−δ2k)})p\in(0,\min\{1, 1.0873(1-δ_{2k}) \}) (Wu et al.).

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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