Innovate isn't really all that hard to define, but I think rephrasing the common definition will place the emphasis on a more useful concept.
The Online Etymology Dictionary states only that the word originated in 1548 and it is based on latin 'in' (into) + 'novus' (new), so it meant 'to renew or change.'
The Random House Dictionary states: to introduce something new (for or as if for the first time), to make changes in anything established.
The American Heritage Dictionary states: to begin or introduc
e (something new) for or as if for the first time.
The Merriam-Webster Dictionary states: to introduce as, or as if, new.
I think the concept of 'introduction' is important to understanding the definition of innovation. It is common to all these sources because, just like any other introduction, it must be done by a person. All innovations originate with an individual who then "introduces" the rest of us to it. This is because an innovation is relative. You can only be introduced to something once, because after the introduction you are familiar with the introduced. An idea can only be new to you the first time you are exposed to it. From then on it is no longer an innovation in your eyes, though it can still be an innovation to someone who has yet to be introduced to it.
Things are only called innovations until they are integrated into a conceptual framework. After a period of adjustment we consider any new idea to be an established part of the environment, and therefore not new. So it is a label applied by an actor, whether they be an individual or a society, when the actor is first introduced to something new.
For this approach to work we must understand it to mean that everyone is first introduced, including the person doing the introducing. The innovator, then, introduces the innovation to themselves first. This is consistent because the important event is the understanding by each individual that something is new; that is the metaphorical moment of introduction.
Therefore, I propose the following definition of innovate: to understand something to be different from anything understood before.
If you feel like researching the topic further Davit Yost, McKinsey and the World Economic Forum, and businessPOV are some resources.