Success probability of the $L_0$-regularized box-constrained Babai point and column permutation strategies
We consider the success probability of the $L_0$-regularized box-constrained Babai point, which is a suboptimal solution to the $L_0$-regularized box-constrained integer least squares problem and can be used for MIMO detection. First, we derive formulas for the success probability of both $L_0$-regularized and unregularized box-constrained Babai points. Then we investigate the properties of the $L_0$-regularized box-constrained Babai point, including the optimality of the regularization parameter, the monotonicity of its success probability, and the monotonicity of the ratio of the two success probabilities. A bound on the success probability of the $L_0$-regularized Babai point is derived. After that, we analyze the effect of the LLL-P permutation strategy on the success probability of the $L_0$-regularized Babai point. Then we propose some success probability based column permutation strategies to increase the success probability of the $L_0$-regularized box-constrained Babai point. Finally, we present numerical tests to confirm our theoretical results and to show the advantage of the $L_0$ regularization and the effectiveness of the proposed column permutation algorithms compared to existing strategies.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
OJBKQ: Objective-Joint Babai-Klein Quantization
Post-training quantization (PTQ) is widely used to compress large language models without retraining. However, many existing weight-only methods rely on heuristic objectives and greedy rounding, thus leading to noticeabl…
GD4: Graph-based Discrete Denoising Diffusion for MIMO Detection
In wireless communications, recovering the optimal solution to the multiple-input multiple-output (MIMO) detection problem is NP-hard. Obtaining high-quality suboptimal solutions with a favorable performance-complexity t…
Reinforcement Learning with Verifiable Rewards: GRPO's Effective Loss, Dynamics, and Success Amplification
Group Relative Policy Optimization (GRPO) was introduced and used successfully to train DeepSeek R1 models for promoting reasoning capabilities of LLMs using verifiable or binary rewards. We show in this paper that GRPO …
The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm
Quantizing the weights of large language models (LLMs) from 16-bit to lower bitwidth is the de facto approach to deploy massive transformers onto more affordable accelerators. While GPTQ emerged as one of the standard me…
The Lattice Geometry of Neural Network Quantization -- A Short Equivalence Proof of GPTQ and Babai's Algorithm
We explain how data-driven quantization of a linear unit in a neural network corresponds to solving the closest vector problem for a certain lattice generated by input data. We prove that the GPTQ algorithm is equivalent…