The Nonconvex Sparse Problem with Nonnegative Constraint for Signal Reconstruction
Access Status
Authors
Date
2016Type
Metadata
Show full item recordAbstract
The problem of finding a sparse solution for linear equations has been investigated extensively in recent years. This is an NPhard 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 nonconvex relaxation rather than by solving its convex relaxation. However, solving the nonconvex relaxation is usually very costive due to the nonconvexity and nonLipschitz continuity of the original problem. This difficulty limits its applications and possible extensions. In this paper, we will consider the nonconvex 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 limitedmemory 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.
Citation
Source Title
Department
Collections
Related items
Showing items related by title, author, creator and subject.

Ruan, Ning (2012)Duality is one of the most successful ideas in modern science [46] [91]. It is essential in natural phenomena, particularly, in physics and mathematics [39] [94] [96]. In this thesis, we consider the canonical duality ...

Mardaneh, Elham (2010)Many industries are beginning to use innovative pricing techniques to improve inventory control, capacity utilisation, and ultimately the profit of the firm. In manufacturing, the coordination of pricing and production ...

Grigoleit, Mark Ted (2008)The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved ...