An official website of the United States government
Modern vector processors support a wide variety of instructions for fixed-point digital signal processing. These instructions support a proliferation of rounding, saturating, and type conversion modes, and are often fused combinations of more primitive operations. While these are common idioms in fixed-point signal processing, it is difficult to use these operations in portable code. It is challenging for programmers to write down portable integer arithmetic in a C-like language that corresponds exactly to one of these instructions, and even more challenging for compilers to recognize when these instructions can be used. Our system, Pitchfork, defines a portable fixed-point intermediate representation, FPIR, that captures common idioms in fixed-point code. FPIR can be used directly by programmers experienced with fixed-point, or Pitchfork can automatically lift from integer operations into FPIR using a term-rewriting system (TRS) composed of verified manual and automatically-synthesized rules. Pitchfork then lowers from FPIR into target-specific fixed-point instructions using a set of target-specific TRSs. We show that this approach improves runtime performance of portably-written fixed-point signal processing code in Halide, across a range of benchmarks, by geomean 1.31× on x86 with AVX2, 1.82× on ARM Neon, and 2.44× on Hexagon HVX compared to a standard LLVM-based compiler flow, while maintaining or improving existing compile times.
more »
« less
A FIXED POINT FRAMEWORK FOR RECOVERING SIGNALS FROM NONLINEAR TRANSFORMATIONS
We consider the problem of recovering a signal from nonlinear transformations, under convex constraints modeling a priori information. Standard feasibility and optimization methods are ill-suited to tackle this problem due to the nonlinearities. We show that, in many common applications, the transformation model can be associated with fixed point equations involving firmly nonexpansive operators. In turn, the recovery problem is reduced to a tractable common fixed point formulation, which is solved efficiently by a provably convergent, block-iterative algorithm. Applications to signal and image recovery are demonstrated. Inconsistent problems are also addressed.
more »
« less
- Award ID(s):
- 1715671
- PAR ID:
- 10229784
- Date Published:
- Journal Name:
- Proceedings of the European Signal Processing Conference
- Volume:
- 2020
- Page Range / eLocation ID:
- 2120-2124
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Recent random block-coordinate fixed point algorithms are particularly well suited to large-scale optimization in signal and image processing. These algorithms feature random sweeping rules to select arbitrarily the blocks of variables that are activated over the course of the iterations and they allow for stochastic errors in the evaluation of the operators. The present paper provides new linear convergence results. These convergence rates are compared to those of standard deter- ministic algorithms both theoretically and experimentally in an image recovery problem.more » « less
-
We consider the problem of recovering a complex vector (up to a global unimodular constant) given noisy and incomplete outer product measurements. Such problems arise when implementing distributed clock synchronization schemes, radar autofocus methods, and phaseless signal recovery. This problem is known as vector synchronization and is a variant of the more common angular synchronization problem. In applications with windowed measurements and/or convolutional models - for example, phase retrieval from STFT magnitude data, the outer product measurement matrix is highly incomplete and has a block diagonal structure. We describe a vector synchronization technique which applies an eigenvector computation to blocks of this matrix followed by a block compatibility operation to piece together the final solution. We provide theoretical guarantees (in the noiseless case) and empirical simulations demonstrating the accuracy and efficiency of the method.more » « less
-
null (Ed.)In this work, we analyze the convergence of constant modulus algorithm (CMA) in blindly recovering multiple signals to facilitate grant-free wireless access. The CMA typically solves a non-convex problem by utilizing stochastic gradient descent. The iterative convergence of CMA can be affected by additive channel noise and finite number of samples, which is a problem not fully investigated previously. We point out the strong similarity between CMA and the Wirtinger Flow (WF) algorithm originally proposed for Phase retrieval. In light of the convergence proof of WF under limited data samples, we adopt the WF algorithm to implement CMA-based blind signal recovery. We generalize the convergence analysis of WF in the context of CMA-based blind signal recovery. Numerical simulation results also corroborate the analysis.more » « less
-
null (Ed.)Abstract Various strategies are available to construct iteratively a common fixed point of nonexpansive operators by activating only a block of operators at each iteration. In the more challenging class of composite fixed point problems involving operators that do not share common fixed points, current methods require the activation of all the operators at each iteration, and the question of maintaining convergence while updating only blocks of operators is open. We propose a method that achieves this goal and analyze its asymptotic behavior. Weak, strong, and linear convergence results are established by exploiting a connection with the theory of concentrating arrays. Applications to several nonlinear and nonsmooth analysis problems are presented, ranging from monotone inclusions and inconsistent feasibility problems, to variational inequalities and minimization problems arising in data science.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/978-9-0827-9705-3
