Error Bounds and a Smoothing Penalty Method for Binary Orthogonal Optimization
Abstract
Binary orthogonal optimization arises in semantic hashing, orthogonal binary projection, and Hadamard matrix design. Existing methods often handle binarity and orthogonality separately, so their outputs need not satisfy both constraints simultaneously and generally come without a residual-based guarantee of exact feasibility. Using an exact box-constrained reformulation, we establish local and global Lipschitz error bounds and prove that the Lipschitz exponent is optimal. In particular, when the binary orthogonal feasible set is nonempty, any box-constrained matrix whose orthogonality residual is below $1$ admits a feasible sign rounding, and the rounding distance is bounded by this residual. These bounds also yield a globally exact nonsmooth orthogonality-residual penalty over the box and a uniformly sharp local penalty threshold. We further develop a smoothing penalty method for binary orthogonal optimization (SPBO). We prove that every accumulation point is stationary for the limiting nonsmooth penalty problem. Numerical experiments on orthogonal binary projection, supervised hashing, and Hadamard completion show that SPBO substantially reduces orthogonality violations while retaining competitive objective values or retrieval accuracy.
Related
- Plug-in Optimization Method for Penalty Parameters in Nonparametric GMANOVA model
- A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
- A nonoverlapping spectral additive Schwarz method for interior penalty discontinuous Galerkin discretizations of Anisotropic Elliptic Problems
- An interior penalty nonconforming finite element method for strain gradient elasticity
- A hybridization-derived interior penalty Nitsche method for heterogeneous and anisotropic diffusion
BibTeX
@misc{lv2026error,
title = {{Error Bounds and a Smoothing Penalty Method for Binary Orthogonal Optimization}},
author = {Ruikai Lv and Lianghai Xiao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14416},
eprint = {2610.14416},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14416},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Error Bounds and a Smoothing Penalty Method for Binary Orthogonal Optimization
AU - Ruikai Lv
AU - Lianghai Xiao
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14416
UR - https://arxiv.org/abs/2610.14416
AB - Binary orthogonal optimization arises in semantic hashing, orthogonal binary projection, and Hadamard matrix design. Existing methods often handle binarity and orthogonality separately, so their outputs need not satisfy both constraints simultaneously and generally come without a residual-based guarantee of exact feasibility. Using an exact box-constrained reformulation, we establish local and global Lipschitz error bounds and prove that the Lipschitz exponent is optimal. In particular, when the binary orthogonal feasible set is nonempty, any box-constrained matrix whose orthogonality residual is below $1$ admits a feasible sign rounding, and the rounding distance is bounded by this residual. These bounds also yield a globally exact nonsmooth orthogonality-residual penalty over the box and a uniformly sharp local penalty threshold. We further develop a smoothing penalty method for binary orthogonal optimization (SPBO). We prove that every accumulation point is stationary for the limiting nonsmooth penalty problem. Numerical experiments on orthogonal binary projection, supervised hashing, and Hadamard completion show that SPBO substantially reduces orthogonality violations while retaining competitive objective values or retrieval accuracy.
ER -