The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction

The problem of finding a sparse solution for linear equations has been investigated extensively in recent years. This is an NP-hard combinatorial problem, and one popular method is to relax such combinatorial requirement into an approximated convex problem, which can avoid the computational complexi...

Full description

Bibliographic Details
Main Authors:	Wang, Y., Zhou, Guanglu, Zhang, X., Liu, W., Caccetta, Louis
Format:	Journal Article
Published:	2016
Online Access:	http://hdl.handle.net/20.500.11937/15730

id	curtin-20.500.11937-15730
recordtype	eprints
spelling	curtin-20.500.11937-157302017-09-13T14:07:14Z The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction Wang, Y. Zhou, Guanglu Zhang, X. Liu, W. Caccetta, Louis The problem of finding a sparse solution for linear equations has been investigated extensively in recent years. This is an NP-hard combinatorial problem, and one popular method is to relax such combinatorial requirement into an approximated convex problem, which can avoid the computational complexity. Recently, it is shown that a sparser solution than the approximated convex solution can be obtained by solving its non-convex relaxation rather than by solving its convex relaxation. However, solving the non-convex relaxation is usually very costive due to the non-convexity and non-Lipschitz continuity of the original problem. This difficulty limits its applications and possible extensions. In this paper, we will consider the non-convex relaxation problem with the nonnegative constraint, which has many applications in signal processing with such reasonable requirement. First, this optimization problem is formulated and equivalently transformed into a Lipschitz continuous problem, which can be solved by many existing optimization methods. This reduces the computational complexity of the original problem significantly. Second, we solve the transformed problem by using an efficient and classical limited-memory Broyden–Fletcher–Goldfarb–Shanno algorithm. Finally, some numerical results show that the proposed method can effectively find a nonnegative sparse solution for the given linear equations with very low computational cost. 2016 Journal Article http://hdl.handle.net/20.500.11937/15730 10.1007/s10957-016-0869-2 restricted
repository_type	Digital Repository
institution_category	Local University
institution	Curtin University Malaysia
building	Curtin Institutional Repository
collection	Online Access
description	The problem of finding a sparse solution for linear equations has been investigated extensively in recent years. This is an NP-hard combinatorial problem, and one popular method is to relax such combinatorial requirement into an approximated convex problem, which can avoid the computational complexity. Recently, it is shown that a sparser solution than the approximated convex solution can be obtained by solving its non-convex relaxation rather than by solving its convex relaxation. However, solving the non-convex relaxation is usually very costive due to the non-convexity and non-Lipschitz continuity of the original problem. This difficulty limits its applications and possible extensions. In this paper, we will consider the non-convex relaxation problem with the nonnegative constraint, which has many applications in signal processing with such reasonable requirement. First, this optimization problem is formulated and equivalently transformed into a Lipschitz continuous problem, which can be solved by many existing optimization methods. This reduces the computational complexity of the original problem significantly. Second, we solve the transformed problem by using an efficient and classical limited-memory Broyden–Fletcher–Goldfarb–Shanno algorithm. Finally, some numerical results show that the proposed method can effectively find a nonnegative sparse solution for the given linear equations with very low computational cost.
format	Journal Article
author	Wang, Y. Zhou, Guanglu Zhang, X. Liu, W. Caccetta, Louis
spellingShingle	Wang, Y. Zhou, Guanglu Zhang, X. Liu, W. Caccetta, Louis The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction
author_facet	Wang, Y. Zhou, Guanglu Zhang, X. Liu, W. Caccetta, Louis
author_sort	Wang, Y.
title	The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction
title_short	The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction
title_full	The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction
title_fullStr	The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction
title_full_unstemmed	The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction
title_sort	non-convex sparse problem with nonnegative constraint for signal reconstruction
publishDate	2016
url	http://hdl.handle.net/20.500.11937/15730
first_indexed	2018-09-06T19:29:23Z
last_indexed	2018-09-06T19:29:23Z
_version_	1610887634734809088

The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction

Similar Items