Volume 32, Issue 4
Equivalence Between Nonnegative Solutions to Partial Sparse and Weighted $l_1$-Norm Minimizations

Xiuqin Tian, Zhengshan Dong & Wenxing Zhu

Ann. Appl. Math., 32 (2016), pp. 380-395.

Published online: 2022-06

Export citation
  • Abstract

Based on the range space property (RSP), the equivalent conditions between nonnegative solutions to the partial sparse and the corresponding weighted $l_1$-norm minimization problem are studied in this paper. Different from other conditions based on the spark property, the mutual coherence, the null space property (NSP) and the restricted isometry property (RIP), the RSP-based conditions are easier to be verified. Moreover, the proposed conditions guarantee not only the strong equivalence, but also the equivalence between the two problems. First, according to the foundation of the strict complementarity theorem of linear programming, a sufficient and necessary condition, satisfying the RSP of the sensing matrix and the full column rank property of the corresponding sub-matrix, is presented for the unique nonnegative solution to the weighted $l_1$-norm minimization problem. Then, based on this condition, the equivalence conditions between the two problems are proposed. Finally, this paper shows that the matrix with the RSP of order $k$ can guarantee the strong equivalence of the two problems.

  • AMS Subject Headings

94A12, 15A29, 90C25

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{AAM-32-380, author = {Tian , XiuqinDong , Zhengshan and Zhu , Wenxing}, title = {Equivalence Between Nonnegative Solutions to Partial Sparse and Weighted $l_1$-Norm Minimizations}, journal = {Annals of Applied Mathematics}, year = {2022}, volume = {32}, number = {4}, pages = {380--395}, abstract = {

Based on the range space property (RSP), the equivalent conditions between nonnegative solutions to the partial sparse and the corresponding weighted $l_1$-norm minimization problem are studied in this paper. Different from other conditions based on the spark property, the mutual coherence, the null space property (NSP) and the restricted isometry property (RIP), the RSP-based conditions are easier to be verified. Moreover, the proposed conditions guarantee not only the strong equivalence, but also the equivalence between the two problems. First, according to the foundation of the strict complementarity theorem of linear programming, a sufficient and necessary condition, satisfying the RSP of the sensing matrix and the full column rank property of the corresponding sub-matrix, is presented for the unique nonnegative solution to the weighted $l_1$-norm minimization problem. Then, based on this condition, the equivalence conditions between the two problems are proposed. Finally, this paper shows that the matrix with the RSP of order $k$ can guarantee the strong equivalence of the two problems.

}, issn = {}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/aam/20650.html} }
TY - JOUR T1 - Equivalence Between Nonnegative Solutions to Partial Sparse and Weighted $l_1$-Norm Minimizations AU - Tian , Xiuqin AU - Dong , Zhengshan AU - Zhu , Wenxing JO - Annals of Applied Mathematics VL - 4 SP - 380 EP - 395 PY - 2022 DA - 2022/06 SN - 32 DO - http://doi.org/ UR - https://global-sci.org/intro/article_detail/aam/20650.html KW - compressed sensing, sparse optimization, range space property, equivalent condition, $l_0$-norm minimization, weighted $l_1$-norm minimization. AB -

Based on the range space property (RSP), the equivalent conditions between nonnegative solutions to the partial sparse and the corresponding weighted $l_1$-norm minimization problem are studied in this paper. Different from other conditions based on the spark property, the mutual coherence, the null space property (NSP) and the restricted isometry property (RIP), the RSP-based conditions are easier to be verified. Moreover, the proposed conditions guarantee not only the strong equivalence, but also the equivalence between the two problems. First, according to the foundation of the strict complementarity theorem of linear programming, a sufficient and necessary condition, satisfying the RSP of the sensing matrix and the full column rank property of the corresponding sub-matrix, is presented for the unique nonnegative solution to the weighted $l_1$-norm minimization problem. Then, based on this condition, the equivalence conditions between the two problems are proposed. Finally, this paper shows that the matrix with the RSP of order $k$ can guarantee the strong equivalence of the two problems.

Xiuqin Tian, Zhengshan Dong & Wenxing Zhu. (2022). Equivalence Between Nonnegative Solutions to Partial Sparse and Weighted $l_1$-Norm Minimizations. Annals of Applied Mathematics. 32 (4). 380-395. doi:
Copy to clipboard
The citation has been copied to your clipboard