Nonconvex penalties with analytical solutions for one-bit compressive sensing

Xiaolin Huang, Ming Yan

Research output: Research - peer-reviewArticle

Abstract

One-bit measurements widely exist in the real world and can be used to recover sparse signals. This task is known as one-bit compressive sensing (1bit-CS). In this paper, we propose novel algorithms based on both convex and non-convex sparsity-inducing penalties for robust 1bit-CS. We consider the dual problem, which has only one variable and provides a sufficient condition to verify whether a solution is globally optimal or not. For positive homogeneous penalties, a globally optimal solution can be obtained in two steps: a proximal operator and a normalization step. For other penalties, we solve the dual problem, and it needs to evaluate the proximal operators for many times. Then we provide fast algorithms for finding analytical solutions for three penalties: minimax concave penalty (MCP), ℓ0 norm, and sorted ℓ1 penalty. Specifically, our algorithm is more than 200 times faster than the existing algorithm for MCP. Its efficiency is comparable to the algorithm for the ℓ1 penalty in time, while its performance is much better than ℓ1. Among these penalties, sorted ℓ1 is most robust to noise in different settings.

LanguageEnglish (US)
Pages341-351
Number of pages11
JournalSignal Processing
Volume144
DOIs
StatePublished - Mar 1 2018

Keywords

  • Analytical solutions
  • Non-convex penalty
  • One-bit compressed sensing

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering

Cite this

Nonconvex penalties with analytical solutions for one-bit compressive sensing. / Huang, Xiaolin; Yan, Ming.

In: Signal Processing, Vol. 144, 01.03.2018, p. 341-351.

Research output: Research - peer-reviewArticle

@article{6a09de7d34604542827c926e613adc94,
title = "Nonconvex penalties with analytical solutions for one-bit compressive sensing",
abstract = "One-bit measurements widely exist in the real world and can be used to recover sparse signals. This task is known as one-bit compressive sensing (1bit-CS). In this paper, we propose novel algorithms based on both convex and non-convex sparsity-inducing penalties for robust 1bit-CS. We consider the dual problem, which has only one variable and provides a sufficient condition to verify whether a solution is globally optimal or not. For positive homogeneous penalties, a globally optimal solution can be obtained in two steps: a proximal operator and a normalization step. For other penalties, we solve the dual problem, and it needs to evaluate the proximal operators for many times. Then we provide fast algorithms for finding analytical solutions for three penalties: minimax concave penalty (MCP), ℓ0 norm, and sorted ℓ1 penalty. Specifically, our algorithm is more than 200 times faster than the existing algorithm for MCP. Its efficiency is comparable to the algorithm for the ℓ1 penalty in time, while its performance is much better than ℓ1. Among these penalties, sorted ℓ1 is most robust to noise in different settings.",
keywords = "Analytical solutions, Non-convex penalty, One-bit compressed sensing",
author = "Xiaolin Huang and Ming Yan",
year = "2018",
month = "3",
doi = "10.1016/j.sigpro.2017.10.023",
volume = "144",
pages = "341--351",
journal = "Signal Processing",
issn = "0165-1684",
publisher = "Elsevier",

}

TY - JOUR

T1 - Nonconvex penalties with analytical solutions for one-bit compressive sensing

AU - Huang,Xiaolin

AU - Yan,Ming

PY - 2018/3/1

Y1 - 2018/3/1

N2 - One-bit measurements widely exist in the real world and can be used to recover sparse signals. This task is known as one-bit compressive sensing (1bit-CS). In this paper, we propose novel algorithms based on both convex and non-convex sparsity-inducing penalties for robust 1bit-CS. We consider the dual problem, which has only one variable and provides a sufficient condition to verify whether a solution is globally optimal or not. For positive homogeneous penalties, a globally optimal solution can be obtained in two steps: a proximal operator and a normalization step. For other penalties, we solve the dual problem, and it needs to evaluate the proximal operators for many times. Then we provide fast algorithms for finding analytical solutions for three penalties: minimax concave penalty (MCP), ℓ0 norm, and sorted ℓ1 penalty. Specifically, our algorithm is more than 200 times faster than the existing algorithm for MCP. Its efficiency is comparable to the algorithm for the ℓ1 penalty in time, while its performance is much better than ℓ1. Among these penalties, sorted ℓ1 is most robust to noise in different settings.

AB - One-bit measurements widely exist in the real world and can be used to recover sparse signals. This task is known as one-bit compressive sensing (1bit-CS). In this paper, we propose novel algorithms based on both convex and non-convex sparsity-inducing penalties for robust 1bit-CS. We consider the dual problem, which has only one variable and provides a sufficient condition to verify whether a solution is globally optimal or not. For positive homogeneous penalties, a globally optimal solution can be obtained in two steps: a proximal operator and a normalization step. For other penalties, we solve the dual problem, and it needs to evaluate the proximal operators for many times. Then we provide fast algorithms for finding analytical solutions for three penalties: minimax concave penalty (MCP), ℓ0 norm, and sorted ℓ1 penalty. Specifically, our algorithm is more than 200 times faster than the existing algorithm for MCP. Its efficiency is comparable to the algorithm for the ℓ1 penalty in time, while its performance is much better than ℓ1. Among these penalties, sorted ℓ1 is most robust to noise in different settings.

KW - Analytical solutions

KW - Non-convex penalty

KW - One-bit compressed sensing

UR - http://www.scopus.com/inward/record.url?scp=85032978374&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85032978374&partnerID=8YFLogxK

U2 - 10.1016/j.sigpro.2017.10.023

DO - 10.1016/j.sigpro.2017.10.023

M3 - Article

VL - 144

SP - 341

EP - 351

JO - Signal Processing

T2 - Signal Processing

JF - Signal Processing

SN - 0165-1684

ER -