Browsing by Author "Chang, Ling-Hua"

Now showing 1 - 14 of 14

Achievable Angles Between Two Compressed Sparse Vectors Under Norm/Distance Constraints Imposed by the Restricted Isometry Property: A Plane Geometry Approach
(2013-04-01)
Chang, Ling-Hua
;
Wu, Jwo-Yuh
;
電機資訊學士班
;
Undergraduate Honors Program of Electrical Engineering and Computer Science
The angle between two compressed sparse vectors subject to the norm/distance constraints imposed by the restricted isometry property (RIP) of the sensingmatrix plays a crucial role in the studies of many compressive sensing (CS) problems. Assuming that 1) u and v are two sparse vectors with (lambda) under bar (u, v) = theta and 2) the sensing matrix Phi satisfies RIP, this paper is aimed at analytically characterizing the achievable angles between Phi u and Phi v. Motivated by geometric interpretations of RIP and with the aid of the well-known law of cosines, we propose a plane-geometry-based formulation for the study of the considered problem. It is shown that all the RIP-induced norm/distance constraints on Phi u and Phi v can be jointly depicted via a simple geometric diagram in the 2-D plane. This allows for a joint analysis of all the considered algebraic constraints from a geometric perspective. By conducting plane geometry analyses based on the constructed diagram, closed-form formulas for the maximal and minimal achievable angles are derived. Computer simulations confirm that the proposed solution is tighter than an existing algebraic-based estimate derived using the polarization identity. The obtained results are used to derive a tighter restricted isometry constant of structured sensing matrices of a certain kind, to wit, those in the form of a product of an orthogonal projection matrix and a random sensing matrix. Follow-up applications in CS are also discussed.
Achievable Angles Between Two Compressed Sparse Vectors Under RIP-Induced Norm/Distance Constraints
(2014-01-01)
Chang, Ling-Hua
;
Wu, Jwo-Yuh
;
電機工程學系
;
Department of Electrical and Computer Engineering
The angle between two compressed sparse vectors subject to the norm/distance constraints imposed by the restricted isometry property (RIP) of the sensing matrix plays an important role in the studies of many compressive sensing (CS) problems. Assuming that (i) u and v are two sparse vectors with measured angle(u, v) = theta and (ii) the sensing matrix satisfies RIP, this paper is aimed at analytically characterizing the achievable angles between u and v. Motivated by geometric interpretations of RIP and with the aid of the well-known law of cosines, we propose a plane geometry based formulation for the study of the considered problem. It is shown that all the RIPinduced norm/distance constraints on u and v can be jointly depicted via a simple geometric diagram in the two-dimensional plane. This allows for a joint analysis of all the involved algebraic constraints from a geometric perspective. By conducting plane geometry analyses based on the constructed diagram, closedform formulae for the maximal and minimal achievable angles are derived. Computer simulations confirm that the proposed solution is tighter than an existing algebraic-based estimate derived using the polarization identity.
An Improved RIP-Based Performance Guarantee for Sparse Signal Reconstruction via Subspace Pursuit
(2014-01-01)
Chang, Ling-Hua
;
Wu, Jwo-Yuh
;
資訊工程學系
;
電機資訊學士班
;
Department of Computer Science
Subspace pursuit (SP) is a well-known greedy algorithm capable of reconstructing a sparse signal vector from a set of incomplete measurements. In this paper, by exploiting an approximate orthogonality condition characterized in terms of the achievable angles between two compressed orthogonal sparse vectors, we show that perfect signal recovery in the noiseless case, as well as stable signal recovery in the noisy case, is guaranteed if the sensing matrix satisfies RIP of order 3K with RIC delta(3K) <= 0.2412. Our work improves the best-known existing results, namely, delta(3K) < 0.165 for the noiseless case [3] and delta(3K) < 0.139 when noise is present [4]. In addition, for the noisy case we derive a reconstruction error upper bound, which is shown to be smaller as compared to the bound reported in [4].
An Improved RIP-Based Performance Guarantee for Sparse Signal Reconstruction with Noise via Orthogonal Matching Pursuit
(2014-01-01)
Chang, Ling-Hua
;
Wu, Jwo-Yuh
;
電信工程研究所
;
Institute of Communications Engineering
Stability of sparse signal reconstruction in the noisy case via orthogonal matching pursuit has been widely studied in the literature of compressive sensing. To guarantee exact support identification under l(2)/l(infinity) -norm bounded noise, sufficient conditions, characterized in terms of the restricted isometry constant and the minimum magnitude of the signal components, were reported in [2]. In this paper, we derive a less conservative set of sufficient conditions of the same kind. Our analyses exploit a newly developed "near-orthogonality" condition, which specifies the achievable angles between two compressed orthogonal sparse vectors. Thus, our improved performance guarantee benefits from more explicit knowledge about the geometry of the compressed space.
An Improved RIP-Based Performance Guarantee for Sparse Signal Recovery via Orthogonal Matching Pursuit
(2014-09-01)
Chang, Ling-Hua
;
Wu, Jwo-Yuh
;
電機工程學系
;
Department of Electrical and Computer Engineering
A sufficient condition reported very recently for perfect recovery of a K-sparse vector via orthogonal matching pursuit (OMP) in K iterations (when there is no noise) is that the restricted isometry constant (RIC) of the sensing matrix satisfies delta(K+1) < (1/root K + 1). In the noisy case, this RIC upper bound along with a requirement on the minimal signal entry magnitude is known to guarantee exact support identification. In this paper, we show that, in the presence of noise, a relaxed RIC upper bound delta(K+1) < (root 4K + 1 - 1/2K) together with a relaxed requirement on the minimal signal entry magnitude suffices to achieve perfect support identification using OMP. In the noiseless case, our result asserts that such a relaxed RIC upper bound can ensure exact support recovery in K iterations: this narrows the gap between the so far best known bound delta(K+1) < (1/root K + 1) and the ultimate performance guarantee delta(K+1) = (1/root K). Our approach relies on a newly established near orthogonality condition, characterized via the achievable angles between two orthogonal sparse vectors upon compression, and, thus, better exploits the knowledge about the geometry of the compressed space. The proposed near orthogonality condition can be also exploited to derive less restricted sufficient conditions for signal reconstruction in two other compressive sensing problems, namely, compressive domain interference cancellation and support identification via the subspace pursuit algorithm.
An Improved RIP-Based Performance Guarantee for Sparse Signal Recovery via Orthogonal Matching Pursuit
(2014-09-01)
Chang, Ling-Hua
;
Wu, Jwo-Yuh
;
交大名義發表
;
電機資訊學士班
;
National Chiao Tung University
A sufficient condition reported very recently for perfect recovery of a K-sparse vector via orthogonal matching pursuit (OMP) in K iterations (when there is no noise) is that the restricted isometry constant (RIC) of the sensing matrix satisfies delta(K+1) < (1/root K + 1). In the noisy case, this RIC upper bound along with a requirement on the minimal signal entry magnitude is known to guarantee exact support identification. In this paper, we show that, in the presence of noise, a relaxed RIC upper bound delta(K+1) < (root 4K + 1 - 1/2K) together with a relaxed requirement on the minimal signal entry magnitude suffices to achieve perfect support identification using OMP. In the noiseless case, our result asserts that such a relaxed RIC upper bound can ensure exact support recovery in K iterations: this narrows the gap between the so far best known bound delta(K+1) < (1/root K + 1) and the ultimate performance guarantee delta(K+1) = (1/root K). Our approach relies on a newly established near orthogonality condition, characterized via the achievable angles between two orthogonal sparse vectors upon compression, and, thus, better exploits the knowledge about the geometry of the compressed space. The proposed near orthogonality condition can be also exploited to derive less restricted sufficient conditions for signal reconstruction in two other compressive sensing problems, namely, compressive domain interference cancellation and support identification via the subspace pursuit algorithm.
Applications of an Exact Formula for the Largest Minimum Distance of Block Codes
(2018-01-01)
Chang, Ling-Hua
;
Wang, Carol
;
Chen, Po-Ning
;
Tan, Vincent Y. F.
;
Han, Yunghsiang S.
An exact information spectrum-type formula for the maximum size of finite length block codes subject to a minimum pairwise distance constraint is presented. This formula can be applied to codes for a broad class of distance measures, which only requires having the minimum value between a point and itself. As revealed by the formula, the largest code size is fully characterized by the information spectrum of the distance between two independent and identically distributed (i.i.d.) random codewords drawn from an optimal distribution. Under an arbitrary uniformly bounded distance measure, the asymptotic largest code rate (in the block length n) attainable for a sequence of (n; M; n delta)-codes is given exactly by the maximum large deviation rate function of the normalized distance between two i.i.d. random codewords.
Channel-Aware Distributed Best-Linear-Unbiased Estimation with Reduced Communication Overheads
(2012)
Wu, Jwo-Yuh
;
Chang, Ling-Hua
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Energy consumption in wireless sensor networks is dominated by intra-network communication dedicated to coordination and information exchange between sensor nodes and the fusion center. The design of distributed estimation algorithms with reduced communication overheads is thus rather crucial. For amplify-and-forward sensor networks over flat fading channels, this paper proposes a new distributed best-linear-unbiased-estimation (BLUE) scheme by exploiting the statistical characterizations of the sensing noise variance and channel gains. The performance measure is the reciprocal of the mean square error averaged over the considered statistical distributions. We derive a closed-form lower bound for the adopted design metric. By means of this result, we further derive a closed-form universal sensor power amplification factor capable of maintaining a target estimation performance. The proposed scheme has the advantage that repeated power scheduling and message feedback are no longer needed in the parameter estimation phase and, hence, the in-network communication cost is further reduced. Some key features regarding the proposed method are discussed. Computer simulations are conducted to evidence our analytic study.
Compressive-Domain Interference Cancellation via Orthogonal Projection: How Small the Restricted Isometry Constant of the Effective Sensing Matrix Can Be?
(2012)
Chang, Ling-Hua
;
Wu, Jwo-Yuh
;
電機工程學系
;
Department of Electrical and Computer Engineering
Knowledge of the achievable restricted isometry constant (RIC) of the sensing matrix is crucial for assessing the signal reconstruction performance of compressive sensing systems. In this paper we consider compressive-domain interference cancellation via orthogonal projection, and study the achievable RIC of the effective sensing matrix, namely, the product of the orthogonal projection matrix and the original sensing matrix. While existing algebraic based methods resorted to the polarization identity to find an upper bound of the considered RIC, motivated by geometric interpretations of the orthogonal projection and the restricted isometry property we derive an improved RIC in a closed form. The proposed solution is shown to be tighter than the existing upper bound. Our analytical results, and the asserted performance advantages, are further evidenced via computer simulations.
Distance Spectrum Formula for the Largest Minimum Hamming Distance of Finite-Length Binary Block Codes
(2017-01-01)
Chang, Ling-Hua
;
Wangl, Carol
;
Chen, Po-Ning
;
Hant, Yunghsiang S.
;
Tang, Vincent Y. F.
In this paper, an exact distance spectrum formula for the largest minimum Hamming distance of finite-length binary block codes is presented. The exact formula indicates that the largest minimum distance of finite-length block codes can be fully characterized by the information spectrum of the Hamming distance between two independent and identically distributed (i.i.d.) random codewords. The distance property of finite-length block codes is then connected to the distance spectrum. A side result of this work is a new lower bound to the largest minimum distance of finite-length block codes. Numerical examinations show that the new lower bound improves the finite-length Gilbert-Varshamov lower bound and can reach the minimum distance of existing finite-length block codes.
Enhanced Noisy Sparse Subspace Clustering via Reweighted L1-Minimization
(2018-01-01)
Wu, Jwo-Yuh
;
Huang, Liang-Chi
;
Yang, Ming-Hsun
;
Chang, Ling-Hua
;
Liu, Chun-Hung
Sparse subspace clustering (SSC) relies on sparse regression for accurate neighbor identification. Inspired by recent progress in compressive sensing (CS), this paper proposes a new sparse regression scheme for SSC via reweighted l(1)-minimization, which also generalizes a twostep l(1)-minimization algorithm introduced by E. J. Candes al all in [The Annals of Statistics, vol. 42, no. 2, pp. 669-699, 2014] without incurring extra complexity burden. To fully exploit the prior information conveyed by the computed sparse vector in the first step, our approach places a weight on each component of the regression vector, and solves a weighted LASSO in the second step. We discuss the impact of weighting on neighbor identification, argue that a popular weighting rule used in CS literature is not suitable for the SSC purpose, and propose a new weighting scheme for enhancing neighbor identification accuracy. Extensive simulation results are provided to validate our discussions and evidence the effectiveness of the proposed approach. Some key issues for future works are also highlighted.
Normalized Weighted Energy Detection for Spectrum Sensing Under Random Primary Signal Arrival
(2017-01-01)
Huang, Pei-Hsin
;
Chang, Ling-Hua
;
Wu, Jwo-Yuh
;
電信工程研究所
;
Institute of Communications Engineering
Cognitive radio (CR) has been identified as an enabling technology toward meeting the high spectrum utilization efficiency demand in future internet-of-things (IoT) systems. Development of new spectrum sensing schemes better suited to CR-based IoT networks, which are typically heterogeneous with perfect network-wide synchronization difficult to achieve, is thus rather crucial. Motivated by the low-complexity feature of the energy detector (ED), this paper proposes a normalized weighted ED to cope with random arrival of the primary user (PU) signal due to imperfect transmission coordination. The proposed approach first multiplies each received sample by a weighting factor, and then normalizes the total weighted energy with respect to the raw signal energy: this is better able to discern the presence of the PU, particularly when the PU arrives very late in the sensing period. The weighting sequence is designed by minimizing the detection probability subject to a tolerable false-alarm probability constraint. In our design, the Gaussian approximation technique is used to derive an approximate formula of the detection probability, and the steepest descent algorithm is used to find a solution. Computer simulations are conducted to validate our analysis, and confirm the performance advantage of the proposed scheme.
On the Maximum Size of Block Codes Subject to a Distance Criterion
(2019-06-01)
Chang, Ling-Hua
;
Chen, Po-Ning
;
Tan, Vincent Y. F.
;
Wang, Carol
;
Han, Yunghsiang S.
We establish a general formula for the maximum size of finite length block codes with minimum pairwise distance no less than d. The achievability argument involves an iterative construction of a set of radius-d balls, each centered at a codeword. We demonstrate that the number of such balls that cover the entire code space cannot exceed this maximum size. Our approach can be applied to codes i) with elements over arbitrary code alphabets, and ii) under a broad class of distance measures. Our formula indicates that the maximum code size can be fully characterized by the cumulative distribution function of the distance measure evaluated at two independent and identically distributed random codewords. When the two random codewords assume a uniform distribution over the entire code alphabet, our formula recovers and thus naturally generalizes the Gilbert-Varshamov (GV) lower bound. Finally, we extend our study to the asymptotic setting.
SPARSE SUBSPACE CLUSTERING WITH SEQUENTIALLY ORDERED AND WEIGHTED L1-MINIMIZATION
(2019-01-01)
Wu, Jwo-Yuh
;
Huang, Liang-Chi
;
Yang, Ming-Hsun
;
Chang, Ling-Hua
;
Liu, Chun-Hung
Built on the sparse representation framework, sparse subspace clustering (SSC) received considerable attention in the recent years. Conventional SSC employs. l(1)-minimization based sparse regression for neighbor identification on a sample-by-sample basis, and is unaware of the neighbor information revealed by those already computed sparse representation vectors. To rid this drawback, this paper proposes a weighted. l(1)-minimization based sparse regression method, and an associated data ordering rule able to reflect the reliability of neighbor information for further enhancing the clustering accuracy. The selection of weighting coefficients for SSC is also discussed. Computer simulations using both the synthesis and real data are provided to evidence the effectiveness of the proposed method.